Proof by inductionAQA A-Level Further Maths: Topic test

1. 1
   For positive integers $n$, let $S_n=\sum_{r=1}^{n}r\times2^{r-1}$. A student is proving by induction that $S_n=(n-1)2^{n}+1$.

   (a)

   Find the value of $S_3$.

   [1 mark]

   • A$12$
   • B$34$
   • C$17$
   • D$13$

   (b)

   Assume the result is true for $n=k$. Which expression is $S_{k+1}$ before any simplification?

   [1 mark]

   • A$(k-1)2^{k}+1+(k+1)2^{k}$
   • B$(k-1)2^{k}+1+k2^{k-1}$
   • C$k2^{k+1}+1+(k+1)2^{k}$
   • D$(k-1)2^{k}+1+(k+1)2^{k+1}$

   (c)

   Show that $(k-1)2^{k}+1+(k+1)2^{k}=k\times2^{k+1}+1$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Let $f(n)=4^{n}+6n-1$, where $n$ is a positive integer. It is to be proved by induction that $f(n)$ is divisible by $9$.

   (a)

   Find the value of $f(3)$.

   [1 mark]

   • A$75$
   • B$81$
   • C$63$
   • D$82$

   (b)

   Which expression is equal to $f(k+1)-4f(k)$?

   [1 mark]

   • A$9(2k-1)$
   • B$9$
   • C$18k+9$
   • D$9(1-2k)$

   (c)

   State the inductive hypothesis, and use $f(k+1)=4f(k)+9(1-2k)$ to show that $f(k+1)$ is divisible by $9$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   The sequence $u_n$ is defined by $u_1=1$, $u_2=3$ and $u_{n+2}=3u_{n+1}-2u_n$ for $n\ge1$. A student suggests that $u_n=2^{n}-1$.

   (a)

   Find $u_3$, $u_4$ and $u_5$, and show that the suggested formula gives the correct value of $u_5$.

   [3 marks]

   (b)

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

   [4 marks]

   Total for question 3: 7 marks

4. 4
   For positive integers $n$, let $T_n=\sum_{r=1}^{n}r\times r!$ and $g(n)=3^{2n+2}-8n-9$.

   (a)

   Prove by induction that $T_n=(n+1)!-1$ for all positive integers $n$.

   [6 marks]

   (b)

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

   [6 marks]

   Total for question 4: 12 marks

5. 5
   The matrix $\mathbf{P}=\begin{pmatrix}2&0\\ 1&1\end{pmatrix}$. A student conjectures that $\mathbf{P}^{n}=\begin{pmatrix}2^{n}&0\\ 2^{n}-1&1\end{pmatrix}$ for positive integers $n$.

   (a)

   Find $\mathbf{P}^2$.

   [1 mark]

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

   (b)

   Assume the conjecture is true for $n=k$. What is the bottom-left entry of $\mathbf{P}^{k+1}=\mathbf{P}^{k}\mathbf{P}$, in its simplest form?

   [1 mark]

   • A$2^{k+1}+1$
   • B$2^{k+1}-1$
   • C$2^{k}$
   • D$2^{k+1}-2$

   (c)

   Complete the proof by induction by writing down the basis step and the final conclusion, assuming that the inductive step has been shown.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   For positive integers $n$, let $S_n=\sum_{r=1}^{n}(2r-1)^2$. A student is proving by induction that $S_n=\frac{n(2n-1)(2n+1)}{3}$.

   (a)

   Find the value of $S_3$.

   [1 mark]

   • A$35$
   • B$25$
   • C$105$
   • D$14$

   (b)

   Assume the result is true for $n=k$. Which expression is $S_{k+1}$ before any simplification?

   [1 mark]

   • A$\frac{k(2k-1)(2k+1)}{3}+(2k-1)^2$
   • B$\frac{k(2k-1)(2k+1)}{3}+(2k+2)^2$
   • C$\frac{k(2k-1)(2k+1)}{3}+(2k+1)^2$
   • D$\frac{(k+1)(2k+1)(2k+3)}{3}+(2k+1)^2$

   (c)

   Show that $\frac{k(2k-1)(2k+1)}{3}+(2k+1)^2=\frac{(k+1)(2k+1)(2k+3)}{3}$.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Let $f(n)=2^{n+2}+3^{2n+1}$, where $n$ is a positive integer. It is to be proved by induction that $f(n)$ is divisible by $7$.

   (a)

   Show that $f(k+1)-2f(k)=7\times3^{2k+1}$.

   [3 marks]

   (b)

   Hence prove by induction that $f(n)$ is divisible by $7$ for all positive integers $n$.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   For positive integers $n$, let $U_n=\sum_{r=1}^{n}r(r+1)(r+2)$ and let $\mathbf{Q}=\begin{pmatrix}3&2\\ -1&0\end{pmatrix}$.

   (a)

   Prove by induction that $U_n=\frac{n(n+1)(n+2)(n+3)}{4}$ for all positive integers $n$.

   [6 marks]

   (b)

   Prove by induction that $\mathbf{Q}^{n}=\begin{pmatrix}2^{n+1}-1&2^{n+1}-2\\ 1-2^{n}&2-2^{n}\end{pmatrix}$ for all positive integers $n$.

   [6 marks]

   Total for question 8: 12 marks

End of questions