common summations

n(n+1)/2

first n natural numbers (nested loop analysis, triangular numbers, handshake problems)

n**2

first n odd numbers (perfect squares, grid problems)

n(n+1)

first n even numbers

n(n+1)(2n+1)/6

first n squares (chessboard)

(n(n+1) / 2)**2

first n cubes

n(n+1)(2n+1)(3n**2+3n-1)/30

first n fourth powers

(r**(n+1) - 1) / (r - 1)

geometric series (1 + r + r**2 + … + r**n) (binary trees, divide and conquer, exponential growth)

1/(1 - r)

infinite geometric series (converging) (probability, EV calculation)

2**(n+1) - 1

first n powers of 2

~ ln(n) + gamma; gamma ~ 0.5772

first n terms of harmonic series (1 + ½ + 1/3 + … + 1/n) (quicksort, hash table, coupon collector)

(n - 1) * 2**(n+1) + 2

first n terms of i * 2**i (algo analysis with doubling)

(n+1)! - 1

first n terms of i * i!

n / (n+1)

first n terms of 1/(i * (i+1)) (telescoping series)

2^n

binomial coefficients (C(n,0) + C(n, 1) + … + C(n, n)) (total subsets of n elements)

0

alternating binomial sum (C(n,0) - C(n,1) + C(n, 2) - … + (-1)**n C(n, n)

n * 2**(n-1)

binomial coefficients * k (C(n,1) + 2*C(n,2) + 3*C(n, 3) + … n*C(n, n))

~1.645

first n 1/i**2 (1 + ¼ + 1/9 + …)

~1.202

first n 1/i**3 (1 + 1/8 + 1/27 + …)

(1 + i)**n

binomial but i geometric? (C(n,0)*i**0 + C(n,1)*i**1 + … + C(n, n)*i**n)