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

Section 1

The four steps of an induction proof

To prove a statement $P(n)$ for all positive integers $n$ :

Basis: show $P(1)$ is true (check both sides of the statement).
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 $P(k)\Rightarrow P(k+1)$ , so $P(n)$ is true for all positive integers $n$ by mathematical induction. The idea is a chain: $P(1)$ gives $P(2)$ , which gives $P(3)$ , and so on. The basis starts the chain; the step keeps it going. Without either, the proof is incomplete.

Key termsbasisinductive stepassumptionconclusion

Common mistake

Assuming the result is true for $n=k+1$ . You assume $n=k$ and must prove $n=k+1$ .

Section 2

Summation of series

The step adds the next term to the assumed sum. Example: prove $\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}{3}$ . For $n=1$ : LHS $=2$ and RHS $=\frac{1\times2\times3}{3}=2$ . Assume true for $n=k$ . Then $\sum_{r=1}^{k+1}r(r+1)=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3},$ which is the formula with $n=k+1$ . The same method proves $\sum_{r=1}^{n}r^3=\frac{n^2(n+1)^2}{4}$ . In the step, factorise out common factors rather than expanding everything.

Key termssummationcommon factor

Exam tip

Write down the target, $P(k+1)$ , before you start so you know the form you are heading for.

Section 3

Divisibility

To prove $f(n)$ is divisible by $m$ : show $f(1)$ is divisible by $m$ , assume $f(k)=m\times\text{integer}$ , and then express $f(k+1)$ using $f(k)$ . Example: $f(n)=3^{2n+1}+1$ is divisible by $4$ . $f(1)=28=4\times7$ . Then $f(k+1)-9f(k)=3^{2k+3}+1-9\left(3^{2k+1}+1\right)=-8$ , so $f(k+1)=9f(k)-8$ . Both terms are multiples of $4$ , so $f(k+1)$ is divisible by $4$ . Another route: if $f(k)=4m$ then $3^{2k+1}=4m-1$ and $f(k+1)=9(4m-1)+1=4(9m-2)$ .

Key termsdivisiblemultiple

Exam tip

Look for $f(k+1)-a\,f(k)$ where $a$ is chosen to cancel the power; the remainder should be a constant multiple of $m$ .

Section 4

General terms of a sequence

If a sequence is defined by $u_{n+1}=g(u_n)$ with $u_1$ given, a formula for $u_n$ is proved by induction. Example: $u_{n+1}=3u_n+4$ with $u_1=1$ , prove $u_n=3^n-2$ . For $n=1$ : $3-2=1$ . Assume $u_k=3^k-2$ . Then $u_{k+1}=3\left(3^k-2\right)+4=3^{k+1}-2$ , which is the formula with $n=k+1$ . The step always substitutes the assumed formula for $u_k$ in the recurrence.

Key termsrecurrence relationgeneral term

Common mistake

Starting the induction at the wrong value: use the given first term, and check the formula against it.

Section 5

Matrix powers

For a $2\times2$ matrix $\mathbf{A}$ , a formula for $\mathbf{A}^n$ is proved by writing $\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}$ and multiplying. Example: $\mathbf{A}=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and $\mathbf{A}^n=\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ . For $n=1$ this is $\mathbf{A}$ . Assume it for $n=k$ ; then $\mathbf{A}^{k+1}=\begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}$ , the formula with $n=k+1$ . Always show all four entries, and compare with the formula with $n$ replaced by $k+1$ .

Key termsmatrix poweridentity

Exam tip

State the conclusion in full every time; examiners award a mark for the complete sentence.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Proof by mathematical induction

A student is proving by induction that $\sum_{r=1}^{n}r=\frac{n(n+1)}{2}$ for all positive integers $n$ , and has already checked the case $n=1$ .
Assuming the result is true for $n=k$ , show that it is true for $n=k+1$ .2 marks
Let $f(n)=7^n-1$ for positive integers $n$ .
Hence, or otherwise, show that if $f(k)$ is divisible by $6$ then $f(k+1)$ is divisible by $6$ .2 marks
A sequence is defined by $u_1=2$ and $u_{n+1}=2u_n+3$ for $n\ge1$ .
Find $u_2$ , $u_3$ and $u_4$ , and verify that the formula $u_n=5\times2^{n-1}-3$ gives the correct values for $n=1,2,3,4$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).