Induction for divisibility and matrix powersAQA A-Level Further Maths: Subtopic test

1. 1
   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$.

   (a)

   Find the value of $f(3)$.

   [1 mark]

   • A$128$
   • B$18$
   • C$125$
   • D$512$

   (b)

   Which statement is the correct inductive hypothesis?

   [1 mark]

   • A$5^{k+1}+3$ is divisible by $4$
   • B$5^k+3=4$
   • C$5^k+3=4k$
   • D$5^k+3=4m$ for some integer $m$

   (c)

   Assuming that $f(k)$ is divisible by $4$, show that $f(k+1)$ is divisible by $4$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   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$.

   (a)

   Find $\mathbf{M}^3$.

   [1 mark]

   • A$\begin{pmatrix}1&8\\ 0&1\end{pmatrix}$
   • B$\begin{pmatrix}1&6\\ 0&1\end{pmatrix}$
   • C$\begin{pmatrix}1&2\\ 0&1\end{pmatrix}$
   • D$\begin{pmatrix}1&6\\ 0&3\end{pmatrix}$

   (b)

   In an inductive proof of the formula, the hypothesis is assumed for $n=k$. Which matrix is $\mathbf{M}^k\mathbf{M}$?

   [1 mark]

   • A$\begin{pmatrix}1&4k\\ 0&1\end{pmatrix}$
   • B$\begin{pmatrix}1&2k\\ 0&1\end{pmatrix}$
   • C$\begin{pmatrix}1&2k+2\\ 0&1\end{pmatrix}$
   • D$\begin{pmatrix}1&2k+2\\ 0&2\end{pmatrix}$

   (c)

   Find the smallest positive integer $n$ for which the top-right entry of $\mathbf{M}^n$ is greater than $1000$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   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$.

   (a)

   Calculate $\mathbf{A}^2$ and $\mathbf{A}^3$, and show that the conjecture is correct for $n=2$ and $n=3$.

   [3 marks]

   (b)

   Prove by induction that the conjecture is true for all positive integers $n$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Let $f(n)=3^{2n}+7$ and $g(n)=n^3+11n$, where $n$ is a positive integer.

   (a)

   Prove by induction that $f(n)$ is divisible by $8$ for all positive integers $n$.

   [6 marks]

   (b)

   Prove by induction that $g(n)$ is divisible by $6$ for all positive integers $n$.

   [6 marks]

   Total for question 4: 12 marks

End of questions