CAIE A-Level Further Math AS 1.7 Proof by induction

[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.
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)$ .
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)$
Multiplies $2 \mathbf{A}^{k}$ with A.

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

5

[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.
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)$ .
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)$
Multiplies $2 \mathbf{A}^{k}$ with A.

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

5

[Maximum number: 7]

The sequence $u_{1}, u_{2}, u_{3}, \ldots$ is such that $u_{1}=1$ and $u_{n+1}=2 u_{n}+1$ for $n \geqslant 1$ .

(a)

Prove by induction that $u_{n}=2^{n}-1$ for all positive integers n.

[ 5 ]

$u_{1}=1=2^{1}-1$
Assume that it is true for n=k, so $u_{k}=2^{k}-1$ .
Then $u_{k+1}=2\left(2^{k}-1\right)+1=2^{k+1}-1$
So, it is also true for n=k+1. Hence, by induction, true for all positive integers.
2a 5

(b)

Deduce that $u_{2 n}$ is divisible by $u_{n}$ for $n \geqslant 1$ .

[ 2 ]

$\frac{u_{2 n}}{u_{n}}=\frac{2^{2 n}-1}{2^{n}-1}=\frac{\left(2^{n}-1\right)\left(2^{n}+1\right)}{\left(2^{n}-1\right)}=2^{n}+1$
2b 2

CAIE A-Level Further Math AS 1.7 Proof By Induction Questions

Exam points

Covered syllabus points

Covered syllabus points

Question 1

Question 2

Question 3

Question (a)

Question (b)