# 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