Proof by mathematical inductionEdexcel A-Level Further Maths: Revision notes

Mathematical induction proves a statement $P(n)$ for every positive integer $n$ by a chain of reasoning, like toppling dominoes. There are four parts, and each earns marks:

• Basis: show $P(1)$ is true by substituting $n=1$ into both sides (or into the expression).
• Assumption: assume $P(k)$ is true for some positive integer $k$.
• Inductive step: use the assumption to show $P(k+1)$ is true.
• Conclusion: state that $P(1)$ is true and that $P(k)$ true implies $P(k+1)$ true, so $P(n)$ is true for all positive integers $n$. The inductive step must use the assumption; proving $P(k+1)$ from scratch is not induction.

For a sum $\sum_{r=1}^{n}u_r$, the inductive step adds the next term to the assumed sum: $\sum_{r=1}^{k+1}u_r=\sum_{r=1}^{k}u_r+u_{k+1}$. Then factorise to reach the formula with $n=k+1$ substituted. Example: prove $\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}{3}$. For $n=1$: $2=\frac{1\times2\times3}{3}$. Assume true for $n=k$: then the sum to $k+1$ terms is $\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)}{3}(k+3)=\frac{(k+1)(k+2)(k+3)}{3}$, the formula with $n=k+1$. The same method proves $\sum r^3=\frac14n^2(n+1)^2$: add $(k+1)^3$ and factorise out $\frac14(k+1)^2$ to get $\frac14(k+1)^2(k+2)^2$.

To prove $\mathrm{f}(n)$ is divisible by $d$: show $\mathrm{f}(1)$ is a multiple of $d$, assume $\mathrm{f}(k)=dm$, then express $\mathrm{f}(k+1)$ as a multiple of $d$. Two reliable routes:

• Form $\mathrm{f}(k+1)-\mathrm{f}(k)$ (or $\mathrm{f}(k+1)-a\,\mathrm{f}(k)$) and show it is a multiple of $d$, so $\mathrm{f}(k+1)=\mathrm{f}(k)+\text{multiple of }d$.
• Substitute the assumed form, e.g. $7^k=6m-5$, directly into $\mathrm{f}(k+1)$. Example: $\mathrm{f}(n)=3^{2n}+11$ divisible by 4. $\mathrm{f}(1)=20$. $\mathrm{f}(k+1)-\mathrm{f}(k)=3^{2k+2}-3^{2k}=8\times3^{2k}$, a multiple of 4. So $\mathrm{f}(k+1)=\mathrm{f}(k)+8\times3^{2k}$ is a multiple of 4.

To prove a formula for $\mathbf{M}^n$, test $n=1$ (the formula must equal $\mathbf{M}$), assume $\mathbf{M}^k$ equals the formula, then calculate $\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}$ (or $\mathbf{M}\mathbf{M}^k$) and simplify each entry. Example: for $\mathbf{M}=\begin{pmatrix}3&-4\\1&-1\end{pmatrix}$, claim $\mathbf{M}^n=\begin{pmatrix}2n+1&-4n\\ n&1-2n\end{pmatrix}$. For $n=1$ it gives $\begin{pmatrix}3&-4\\1&-1\end{pmatrix}$. Then $\mathbf{M}^{k+1}=\begin{pmatrix}2k+1&-4k\\ k&1-2k\end{pmatrix}\begin{pmatrix}3&-4\\1&-1\end{pmatrix}$ has top-left entry $3(2k+1)-4k=2k+3=2(k+1)+1$, as required. Check all four entries and say they match. Matrix multiplication is not commutative in general, but $\mathbf{M}^k\mathbf{M}=\mathbf{M}\mathbf{M}^k$, so either order is acceptable here.

Examiners award a mark for the full conclusion. A model sentence: 'The statement is true for $n=1$, and if it is true for $n=k$ then it is true for $n=k+1$. Therefore it is true for all positive integers $n$ by mathematical induction.' Partial wording such as 'so it is true for all $n$' is not enough. In a 'show that' inductive step, write the expression for $k+1$, substitute the assumption, simplify, and state that this is the required form. If the question starts from $n=0$ or another value, use that as the basis and amend the final sentence.