Copyright © University of Cambridge. All rights reserved.
You are probably already familiar with the formula for the triangular numbers: $$\sum_{i=1}^{n} i = \frac{1}{2}n(n+1).$$
As with many mathematical statements involving sums of integers, this can be proved using induction:
Base case $(n=1)$:
LHS $=\sum_{i=1}^1 i = 1$
RHS $= \frac{1}{2}(1\times2) = 1$
So LHS=RHS.
Inductive step:
Assume true for $n=k$: $$\sum_{i=1}^{k} i = \frac{1}{2}k(k+1)$$When $n=(k+1)$:
$$\begin{align} \text{LHS} &= \sum_{i=1}^{k+1} i \\
&= \sum_{i=1}^k i + (k+1) \\
&= \frac{1}{2}k(k+1) + (k+1) \quad\text{(by induction hypothesis)}\\
&= \frac{1}{2}\lbrace k(k+1) + 2(k+1) \rbrace \\
&= \frac{1}{2}(k+1)(k+2) \quad\text{(taking out common factor of (k+1))}\end{align}$$
This is the correct form for the right hand side for the case $n=k+1$.
We have shown the formula to be true for $n=1$, and we have shown that if true for $n=k$ it also holds for $n=k+1$. Therefore, by induction, it is true for all natural numbers $n$.
Have a go at proving the following familiar formulae by induction. Try to set it out in the same way as the example above.
$$\sum_{i=1}^n i^2 = \frac{1}{6}n(n+1) (2n+1)$$
$$\sum_{i=1}^n i^3 = \left[\frac{n(n+1)}{2}\right]^2$$
Some common mistakes
Check that you haven't forgotten to prove the base case! This is the most common mistake in induction proofs.
Have you finished your proof off properly? Make sure you have clearly shown the inductive step.
Having trouble getting the inductive step to work out? Check for really obvious algebraic errors. On occasion, I have spent minutes getting bogged down in a question because I've failed to multiply out a set of brackets correctly! A quick way of spotting which line contains the error is to do a sanity check with some small numbers.
Another example
The following is taken from the NRICH problem OK! Now Prove It:
Notice that $$1^2 = {1\times 2\times 3 \over 6}$$ $$1^2 + 3^2 = {3\times 4\times 5 \over 6}$$ $$1^2 + 3^2 + 5^2 = {5\times 6\times 7 \over 6}.$$ Make a conjecture about the sum $$1^2 + 3^2 + 5^2 + \dots + (2n - 1)^2$$ and prove your conjecture.
Have a go at the problem, and then take a look at
this solution showing how to set out a proof by induction.
By now, you should be getting the hang of proof by induction, so why not try some more problems from
STEP Prep Module 9?