Big sums everywhere

Exercise 1.1

Prove that for every natural number n the following identities hold.

\begin{align} \sum_{i=0}^n i & = \frac{n(n+1)}{2} \\ \sum_{i=0}^n i^2 & = \frac{n(n+1)(2n+1)}{6} \\ \sum_{i=0}^n 2^i &= 2^{n+1}-1 \end{align}

Hint

Recall that, for a function f: \mathbb N\to \mathbb R, the notation \displaystyle \sum_{i=0}^n f(i) is just a shortcut for the sum f(0)+f(1)+\cdots+f(n-1)+f(n). For instance \displaystyle\sum_{i=0}^n i^2 is just a more compact (and precise) way to denote 0^2+1^2+2^2+\cdots+(n-1)^2+n^2.

One systematic way to prove the equalities in this exercise is to use induction on n.

---

Extra

Other useful equalities: \begin{align} \sum_{i=0}^n i^3 & = \left(\sum_{i=0}^n i\right)^2 = \frac{n^2(n+1)^2}{4} \\ \sum_{i=0}^n i^k & = \Theta(n^{k+1}) \end{align}

Important

It is important to remember/memorize the equalities in this exercise: they will arise naturally in analyzing the cost of for/while loops of C++ programs, e.g. in Exercise 1.12.