Checking $1 + 3 + 5 = 9 = 3^2$ and $1 + 3 + 5 + 7 = 16 = 4^2$ suggests a pattern, but no number of examples proves it for every $n$. Mathematical induction does. It is the standard way to prove statements about sums and other patterns indexed by whole numbers.
Key idea
To prove a statement $S(n)$ for all $n \ge 1$: (1) Base case: show $S(1)$ is true. (2) Inductive step: assume $S(k)$ is true for some $k \ge 1$ (the inductive hypothesis) and use it to show $S(k + 1)$ is true. Then $S(n)$ holds for every $n \ge 1$.
Why it works
Picture an endless line of dominoes. The base case knocks over the first one. The inductive step guarantees that whenever one falls, the next one falls too. So the second falls, then the third, and so on forever. In logical terms: if some $n$ failed, look at the smallest such $n$. It is not $1$, so $n - 1$ works, and the inductive step then makes $n$ work, a contradiction.
Worked examples
Worked example: Sum of odd numbers
Prove $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for all $n \ge 1$.
- Base case: for $n = 1$ the left side is $1$ and the right side is $1^2 = 1$. ✓
- Inductive step: assume $1 + 3 + \cdots + (2k - 1) = k^2$. The next odd number is $2(k + 1) - 1 = 2k + 1$.
- Add it to both sides: $$1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.$$
- That is the statement for $n = k + 1$, so by induction it holds for every $n$.
Answer: Proved
Worked example: Sum of the first $n$ numbers
Show the inductive step for $1 + 2 + \cdots + n = \dfrac{n(n + 1)}{2}$.
- Assume $1 + 2 + \cdots + k = \dfrac{k(k + 1)}{2}$. Add the next term, $k + 1$, to both sides.
- Right side: $$\dfrac{k(k + 1)}{2} + (k + 1) = \dfrac{k(k + 1) + 2(k + 1)}{2} = \dfrac{(k + 1)(k + 2)}{2}.$$
- That is the formula with $n = k + 1$. (The base case: $1 = \frac{1 \cdot 2}{2}$.)
Answer: The step works, so the formula holds for all $n \ge 1$
Worked example: Divisibility
Prove that $3$ divides $4^n - 1$ for all $n \ge 1$.
- Base: $4^1 - 1 = 3$. ✓
- Assume $4^k - 1$ is a multiple of $3$. Then $$4^{k+1} - 1 = 4 \cdot 4^k - 4 + 3 = 4(4^k - 1) + 3.$$
- Both $4(4^k - 1)$ and $3$ are multiples of $3$, so their sum is too.
Answer: Proved
Common mistake
Two common errors. Skipping the base case: the step alone can "prove" false statements, such as $n = n + 1$ (if $k = k + 1$ then $k + 1 = k + 2$), because no first domino ever falls. And assuming the conclusion: writing down $S(k + 1)$ and simplifying it until it looks true proves nothing. The step must start from $S(k)$ and arrive at $S(k + 1)$.