Proving Summation Formulas by Induction

Many series that appear throughout algebra and calculus -- sums of consecutive natural numbers, their squares, their cubes, geometric progressions, and telescoping fractions -- have a compact closed-form total. Mathematical induction is the standard, fully rigorous way to prove such a formula holds for every natural number $n$, not just the handful of small cases you might check by hand.

The general pattern. To prove a summation formula $S(n) = f(n)$ by induction: (i) verify the base case $S(1) = f(1)$ directly; (ii) assume the inductive hypothesis $S(k) = f(k)$ for some $k \ge 1$; (iii) write $S(k+1) = S(k) + a_{k+1}$, where $a_{k+1}$ is the $(k+1)$-th term of the series being summed, substitute the inductive hypothesis for $S(k)$, and show algebraically that the result simplifies to $f(k+1)$.

Worked example. We prove, in full, that

Proof. Let $P(n)$ denote the statement $1+2+\cdots+n = \dfrac{n(n+1)}{2}$.

Base case. For $n=1$, the left side is simply $1$, and the right side is $\dfrac{1(1+1)}{2} = \dfrac{2}{2} = 1$. Since both sides equal $1$, $P(1)$ is true.

Inductive step. Assume $P(k)$ is true for some $k \ge 1$, i.e.

We must show $P(k+1)$ holds, i.e. $1+2+\cdots+k+(k+1) = \dfrac{(k+1)(k+2)}{2}$. Starting from the left side of $P(k+1)$ and using the inductive hypothesis to replace the first $k$ terms:

This is exactly the right side of $P(k+1)$, so $P(k+1)$ is true. …