Closed Forms for Common Summations
Sum of Constants
$$ \sum^{n-1}_{i=0} 1 = \sum^{n}_{i=1} 1 = n $$
| \( i \) | loop value |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 1 |
| \( \dots{} \) | \( \dots{} \) |
| \( n - 1 \) | 1 |
| (sum) | \( 1 + 1 + 1 + \cdots{} + 1 = n \) |
Counting Up
$$ \sum^{n}_{i=1} i = \frac{n ( n + 1) }{2} $$
| \( i \) | loop value |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
| \( \dots{} \) | \( \dots{} \) |
| \( n \) | \( n \) |
| (sum) | \( 1 + 2 + 3 + 4 + 5 + 6 + \dots{} + n = \frac{ n ( n + 1 ) }{ 2 } \) |
Sum of Powers
$$ \sum^{\log_{m}{n}}_{i=1} m^{i} = \frac{ m }{ m - 1 } ( n - 1 ) $$
For example,
$$ \sum^{\log_{2}{n}}_{i=1} 2^{i} = 2n - 2 $$
| \( i \) | loop value |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| \( \dots{} \) | \( \dots{} \) |
| \( \log_{2}{n} \) | \( 2^{\log_{2}{n}} = n \) |
Sum of Reciprocals
$$ \sum^{n}_{i=1} \frac{1}{i} = H(n) \approx \ln{n} $$
| \( i \) | loop variable |
|---|---|
| 1 | 1 |
| 2 | \( \frac{1}{2} \) |
| 3 | \( \frac{1}{3} \) |
| \( \dots{} \) | \( \dots{} \) |
| \( n \) | \( \frac{1}{n} \) |
| (sum) | \( 1 + \frac{1}{3} + \frac{1}{3} + \cdots{} + \frac{1}{n} = H(n) \approx \ln{n} \) |
(When logged in, completion status appears here.)