Mathematical Induction — Applications to Summation and Divisibility

The Principle of Mathematical Induction is applied in this chapter to two standard classes of results.

Summation formulas. A claim of the form $1+2+\cdots+n = \dfrac{n(n+1)}{2}$, or $1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}$, is proved by: (i) checking the formula at $n=1$; (ii) assuming it holds for $n=k$; (iii) adding the next term, $(k+1)$ or $(k+1)^2$ as the case may be, to both the assumed sum and the assumed formula, and showing through algebraic simplification that the result is exactly the original formula with $n$ replaced by $k+1$.

Divisibility results. A claim of the form "$f(n)$ is divisible by $d$ for every natural number $n$" is proved by: (i) checking $f(1)$ is divisible by $d$; (ii) assuming $f(k) = d \cdot m$ for some integer $m$; (iii) expressing $f(k+1)$ in terms of $f(k)$ (typically by adding and subtracting a term so that $f(k)$ appears explicitly), and showing that what remains, after substituting $f(k)=dm$, is still a multiple of $d$. …