| 1. Σ i=a to z, 1 = z - a + 1; Σ i=1 to n, 1 = n | 2. Σ i=1 to n, i = 1 + 2 + 3 + . . . + n = n(n+1)/2 ≈ 1/2 n2 |
3. Σ i=1 to n, i2 =
12 + 22 + 32 + . . . +
n2 =
n(n+1)(2n+1)
------------ ≈ 1/3 n3
6
|
4. Σ i=1 to n, ik =
1k + 2k + 3k + . . . + nk
≈ 1
---- nk+1
k+1
|
5. Σ i=0 to n, ai = 1 + a + . . . an =
an+1 - 1
-------- (a ≠ 1)
a - 1
|
5a. Σ i=0 to n, 2i = 2n+1 - 1
(This is the value of a binary number of size n+1 bits, with all bits flipped on.) |
|
6. Σ i=1 to n, i 2i = 1 * 2 + 2 * 22 + . . . + n * 2n =
(n - 1)2n+1 + 2 |
7. Σ i=1 to n, 1/i = 1/1 + 1/2 + 1/3 + . . . + 1/n ≈ ln n +
γ, where γ ≈ 0.5772 . . . (Euler's constant) |
| 8. Σ i=1 to n, lg i ≈ n lg n , where lg is log base 2 |
Modular Arithmetic Formulas, where n, m are integers, and p is a positive integer
|
n mod m = 1 is also n - 1 mod m = 0 Example: 5 mod 4 = 1 == 4 mod 4 = 0. |
Product Rule. (n * m) mod p = ((n mod p) * (m mod p)) mod p Additive Rule. (n + m) mod p = (n mod p + m mod p) mod p |
Log and Exponentiation Rules
loga(n) = loga(b) * logb(n)
log2 (10) = 3.0129996
if n=2^k then k = lg n
log(n^k) = k log (n)
log(nm) = log (m) + log (n)
pm(n-1) pm = pmn
pmpn = pm+n
Floor and Ceiling Formulas
| floor(n/2) + ceiling(n/2) = n, for all integers n | floor(x+n) = floor(x) + n and ceil(x+n) = ceil(x) + n, for real x and integer n |
| ceil(lg(n + 1)) = floor(lg n) + 1 | b = floor (lg n) + 1, where b is the number of bits in the binary representation of n |
Miscellaneous Stuff
| Stirling's approx. for n! is (n/3)^n < n! < (n/2)^n for n >= 6. |