Useful sums and formulas

In algorithmic challenges you may very often meet problems that are somehow related to mathematical series, distributions, or combinatorics. As I not always remeber all the formulas I have created a quick reference.

1. Arithmetic Progression and Series

a) Sum
S_n = \frac{n}{2}(a_1 + a_n)
b) N-th element of the progression
a_n = a_1 + (n-1)d
Where r stands for the difference

2. Geometric Progression and Series

a) Sum
S_n = a_1\frac{(1 - r^n)}{1-r}
b) N-th element of progression
a_n = a_1 * r ^ n
Where r stands for ratio.

3. Gauss sum
\sum\limits_{k=1}^n k = \frac{n(n + 1)}{2}

4. Gauss series
\sum\limits_{k=1}^{\infty} (k+1)z^k = \frac{1}{(1 - z)^2}

5. Sum of squares
\sum\limits_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

6. Factorials sum
\sum\limits_{k=0}^{n} k(k+1) = \frac{n(n+1)(n+2)}{3}

7. Binomial theorem
\sum\limits_{k=0}^{n}  \binom {n} {k}x^ky^{n-k} = (x+y)^n

8. Harmonic function
ln( \frac{1}{1-z})= \sum\limits_{k=0}^{\infty}(z^k/k)

In the next article we will summarise probability.

Best Regards

Joe Kidd