Note 3: Sums

In the last post, we talked about proof by induction, and showed an example proof that made heavy use of summation notation. In this quick post, we’re going to list a few important sums that you should study. They’re mostly important because they show up in actual analyses of algorithms. They’re also important because they may show up on quizzes and exams. In no particular order:

$\sum_{i = 1}^n i = \frac{n(n+1)}{2}$ . You can prove this one by induction.
$\sum_{0 \le k \le n} x^k = \frac{1 - x^{n+1}}{1 - x}$ , when $x \ne 0$ . You can prove this one using a “telescoping sums” argument.
$\sum_{k \ge 0} x^k = \frac{1}{1-x}$ , when $0 < |x| < 1$ . You can prove this one by taking limits.
$\sum_{1 \le k \le n} \frac{1}{k} \approx \log(n)$ . You can work this out with an integral approximation.
$\sum_{1 \le k \le n} \log(k) \approx n \log(n)$ . You can work this out with an integral approximation.
$\sum_{1 \le k \le n} k^p \approx \frac{n^{p+1}}{p+1}$ , where $p$ is a constant. Integrals again.