Induction for divisibility and matrix powersAQA A-Level Further Maths: Revision notes

Section 1

Setting up a divisibility proof

To prove that $f(n)$ is divisible by $d$ for all positive integers $n$ :

Basis: show $f(1)$ is a multiple of $d$ .
Hypothesis: assume $f(k)=dm$ for some integer $m$ .
Step: show $f(k+1)$ is also a multiple of $d$ , that is $f(k+1)=d\times(\text{an integer expression})$ .
Conclusion: the standard statement: true for $n=1$ , true for $n=k$ implies true for $n=k+1$ , so true for all positive integers $n$ by induction. Writing the hypothesis as an equation $f(k)=dm$ lets you substitute it. ‘Assume $f(k)$ is divisible by $d$ ’ on its own gives you nothing to use.

Key termsdivisibleinteger multiple

Common mistake

Writing ‘assume $f(k)=d$ ’ or ‘ $f(k)=dk$ ’. The multiple $m$ is an unknown integer, not a fixed number or $k$ .

Section 2

Two ways to complete the step

Method 1: the difference. Calculate $f(k+1)-f(k)$ , show it is a multiple of $d$ , then $f(k+1)=f(k)+(\text{multiple of }d)=dm+(\text{multiple of }d)$ , a multiple of $d$ . Method 2: substitute. Rewrite the power in terms of $m$ using the hypothesis, e.g. $5^k=4m-3$ , then $f(k+1)=5\times5^k+3=5(4m-3)+3=4(5m-3)$ . Useful differences: $5^{k+1}-5^k=4\times5^k$ and $7^{k+1}-7^k=6\times7^k$ .

Key termsdifference method

Exam tip

For $a^n\pm b$ , factorise $a^{k+1}-a^k=a^k(a-1)$ . The factor $(a-1)$ often carries the divisor.

Section 3

Worked example: powers

Prove that $7^n-1$ is divisible by $6$ for all positive integers $n$ . Basis: $n=1$ : $7-1=6=6\times1$ . Hypothesis: assume $7^k-1=6m$ for some integer $m$ . Step: $7^{k+1}-1=7\times7^k-1=7(6m+1)-1=42m+6=6(7m+1)$ , a multiple of $6$ . Conclusion: true for $n=1$ , and true for $n=k$ implies true for $n=k+1$ , so true for all positive integers $n$ by induction.

Common mistake

Dropping the constant when rewriting: $7^k=6m+1$ , not $6m$ .

Section 4

Divisibility of polynomial expressions

For $g(n)=n^3+11n$ (divisible by $6$ ): $g(k+1)-g(k)=3k^2+3k+12=3k(k+1)+12$ . The product $k(k+1)$ of two consecutive integers is always even, so $k(k+1)=2j$ and $3k(k+1)=6j$ . Hence $g(k+1)=6m+6j+12=6(m+j+2)$ . State the reason $k(k+1)$ is even: one of two consecutive integers is even.

Key termsconsecutive integers

Exam tip

Expand $(k+1)^3=k^3+3k^2+3k+1$ carefully before subtracting.

Section 5

Proving formulae for powers of a matrix

To prove a formula for $\mathbf{M}^n$ , check $n=1$ , assume $\mathbf{M}^k$ equals the formula, then use $\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}$ and multiply the matrices. Example: $\mathbf{M}=\begin{pmatrix}1&2\\ 0&1\end{pmatrix}$ , claim $\mathbf{M}^n=\begin{pmatrix}1&2n\\ 0&1\end{pmatrix}$ . Basis: $n=1$ gives $\mathbf{M}$ . Step: $\mathbf{M}^{k+1}=\begin{pmatrix}1&2k\\ 0&1\end{pmatrix}\begin{pmatrix}1&2\\ 0&1\end{pmatrix}=\begin{pmatrix}1&2k+2\\ 0&1\end{pmatrix}=\begin{pmatrix}1&2(k+1)\\ 0&1\end{pmatrix}$ . The result is the formula with $n=k+1$ , so the induction is complete.

Key termsmatrix power

Exam tip

Calculate $\mathbf{M}^2$ and $\mathbf{M}^3$ first to spot the pattern, then prove it. Check every entry in the step, not just one.

Section 6

Presenting the final answer

For matrices, show that every entry matches the formula with $n=k+1$ (for example $1+2(k+1)$ , not just $3+2k$ ). For divisibility, the last line must be $f(k+1)=d\times(\text{integer})$ , naming the integer expression. Always include the full conclusion. Marks are lost for ‘so true for all $n$ ’ without the basis and the inductive link.

Common mistake

Multiplying in the wrong order for matrices. Use $\mathbf{M}^k\mathbf{M}$ (or $\mathbf{M}\mathbf{M}^k$ ) consistently and keep the rows and columns right.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Induction for divisibility and matrix powers

Let $f(n)=5^n+3$ for positive integers $n$ . It is to be proved by induction that $f(n)$ is divisible by $4$ for all $n$ .
Assuming that $f(k)$ is divisible by $4$ , show that $f(k+1)$ is divisible by $4$ .2 marks
The matrix $\mathbf{M}=\begin{pmatrix}1&2\\ 0&1\end{pmatrix}$ satisfies $\mathbf{M}^n=\begin{pmatrix}1&2n\\ 0&1\end{pmatrix}$ for every positive integer $n$ .
Find the smallest positive integer $n$ for which the top-right entry of $\mathbf{M}^n$ is greater than $1000$ .2 marks
Let $\mathbf{A}=\begin{pmatrix}3&-2\\ 2&-1\end{pmatrix}$ . A student conjectures that $\mathbf{A}^n=\begin{pmatrix}1+2n&-2n\\ 2n&1-2n\end{pmatrix}$ for all positive integers $n$ .
Calculate $\mathbf{A}^2$ and $\mathbf{A}^3$ , and show that the conjecture is correct for $n=2$ and $n=3$ .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).