CAIE A-Level Further Mathematics 1.7.1 Proof by Induction

Practise complete induction proofs for formulae, recurrences, inequalities and divisibility, with a valid base case, hypothesis and explicit k-to-k-plus-one step.

Exam points

verify the stated base case and write the inductive hypothesis for a positive integer k
use the hypothesis in the k-plus-one expression and simplify it to the required target form
finish with an explicit induction conclusion after proving the inequality or divisibility step

[Maximum number: 5]

Let $\mathbf{A}=\left(\begin{array}{ll}3 & 0 \\ 1 & 1\end{array}\right)$ .

Prove by mathematical induction that, for all positive integers n,

2 \mathbf{A}^{n}=\left(\begin{array}{ll} 2 \times 3^{n} & 0 \\ 3^{n}-1 & 2 \end{array}\right) .

$2 \mathbf{A}=\left(\begin{array}{ll}6 2 2\end{array}\right)=\left(\begin{array}{ll}2 \times 3 3-1 2\end{array}\right)$ so true when n=1.

B1

States base case.

Assume that it is true for n=k, so $2 \mathbf{A}^{k}=\left(\begin{array}{ll}2 \times 3^{k} 3^{k}-1 2\end{array}\right)$ .

B1

States inductive hypothesis.

Then $2 \mathbf{A}^{k+1}=\left(\begin{array}{ll}2 \times 3^{k} 3^{k}-1 2\end{array}\right)\left(\begin{array}{ll}3 1 1\end{array}\right)=\left(\begin{array}{cc}2 \times 3^{k+1} 3^{k+1}-3+2 2\end{array}\right)$

M1A1

Multiplies $2 \mathbf{A}^{k}$ with A.

So, it is also true for n=k+1. Hence, by induction, true for all positive integers.

A1

States conclusion.

5

All question bank results loaded

1.7.1—Proof by induction question 1