# Exercises - Induction and Sums

### Part I

Use mathematical induction to prove the following statements hold for every positive integer $n$.

1. $\displaystyle{\sum_{i=1}^{n} i = \frac{n(n+1)}{2}}$ 2. $\displaystyle{\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}}$ 3. $\displaystyle{\sum_{i=1}^{n} i^3 = \frac{n^2 (n+1)^2}{4}}$ 4. $\displaystyle{\sum_{i=1}^{n} i^4 = \frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}}$ ### Part II

Prove the following statements hold for every positive integer $n$ in two ways: 1) with mathematical induction; and 2) using the results proven in problems 1-4 above.

1. $\displaystyle{\sum_{i=1}^{n} (2i-1) = n^2}$ 2. $\displaystyle{\sum_{i=1}^{n} 2i = n^2 + n}$ 3. $\displaystyle{\sum_{i=1}^{n} (2i-1)^2 = \frac{4n^3-n}{3}}$ 4. $\displaystyle{\sum_{i=1}^{n} i(i+1) = \frac{n (n+1) (n+2)}{3}}$ ### Part III (Challenge!) Are you curious how someone might have initially figured out the formulas for the various summations in (a)-(d)? Find a formula for $\sum_{i=1}^{n} i^3$ by using the following fact in combination with the results of problems 1-2 in Part I.

$$\left[ \sum_{i=1}^{n} i^4 \right] + (n+1)^4 = \sum_{i=0}^{n} (i+1)^4$$

Then, state a similar fact that can be used to find $\sum_{i=1}^{n} i^4$.

◆ ◆ ◆