# 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$.

◆ ◆ ◆