Proof by induction

Proof by induction topic test

AQA A-Level Further Maths: covers all 2 subtopics

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 20 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

20 questions, 54 marks

AQA A-Level Further Maths

Proof by induction topic test

Total 54 marks

Name

Class

Date

  1. 1
    For positive integers nn, let Sn=∑r=1nr×2r−1S_n=\sum_{r=1}^{n}r\times2^{r-1}. A student is proving by induction that Sn=(n−1)2n+1S_n=(n-1)2^{n}+1.
    (a)
    Find the value of S3S_3.
    [1 mark]
    • A1212
    • B3434
    • C1717
    • D1313
    (b)
    Assume the result is true for n=kn=k. Which expression is Sk+1S_{k+1} before any simplification?
    [1 mark]
    • A(k−1)2k+1+(k+1)2k(k-1)2^{k}+1+(k+1)2^{k}
    • B(k−1)2k+1+k2k−1(k-1)2^{k}+1+k2^{k-1}
    • Ck2k+1+1+(k+1)2kk2^{k+1}+1+(k+1)2^{k}
    • D(k−1)2k+1+(k+1)2k+1(k-1)2^{k}+1+(k+1)2^{k+1}
    (c)
    Show that (k−1)2k+1+(k+1)2k=k×2k+1+1(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)=4n+6n−1f(n)=4^{n}+6n-1, where nn is a positive integer. It is to be proved by induction that f(n)f(n) is divisible by 99.
    (a)
    Find the value of f(3)f(3).
    [1 mark]
    • A7575
    • B8181
    • C6363
    • D8282
    (b)
    Which expression is equal to f(k+1)−4f(k)f(k+1)-4f(k)?
    [1 mark]
    • A9(2k−1)9(2k-1)
    • B99
    • C18k+918k+9
    • D9(1−2k)9(1-2k)
    (c)
    State the inductive hypothesis, and use f(k+1)=4f(k)+9(1−2k)f(k+1)=4f(k)+9(1-2k) to show that f(k+1)f(k+1) is divisible by 99.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    The sequence unu_n is defined by u1=1u_1=1, u2=3u_2=3 and un+2=3un+1−2unu_{n+2}=3u_{n+1}-2u_n for n≥1n\ge1. A student suggests that un=2n−1u_n=2^{n}-1.
    (a)
    Find u3u_3, u4u_4 and u5u_5, and show that the suggested formula gives the correct value of u5u_5.
    [3 marks]
    (b)
    Prove by induction that un=2n−1u_n=2^{n}-1 for all positive integers nn.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    For positive integers nn, let Tn=∑r=1nr×r!T_n=\sum_{r=1}^{n}r\times r! and g(n)=32n+2−8n−9g(n)=3^{2n+2}-8n-9.
    (a)
    Prove by induction that Tn=(n+1)!−1T_n=(n+1)!-1 for all positive integers nn.
    [6 marks]
    (b)
    Prove by induction that g(n)g(n) is divisible by 6464 for all positive integers nn.
    [6 marks]

    Total for question 4: 12 marks

  5. 5
    The matrix P=(2011)\mathbf{P}=\begin{pmatrix}2&0\\ 1&1\end{pmatrix}. A student conjectures that Pn=(2n02n−11)\mathbf{P}^{n}=\begin{pmatrix}2^{n}&0\\ 2^{n}-1&1\end{pmatrix} for positive integers nn.
    (a)
    Find P2\mathbf{P}^2.
    [1 mark]
    • A(4011)\begin{pmatrix}4&0\\ 1&1\end{pmatrix}
    • B(4021)\begin{pmatrix}4&0\\ 2&1\end{pmatrix}
    • C(4131)\begin{pmatrix}4&1\\ 3&1\end{pmatrix}
    • D(4031)\begin{pmatrix}4&0\\ 3&1\end{pmatrix}
    (b)
    Assume the conjecture is true for n=kn=k. What is the bottom-left entry of Pk+1=PkP\mathbf{P}^{k+1}=\mathbf{P}^{k}\mathbf{P}, in its simplest form?
    [1 mark]
    • A2k+1+12^{k+1}+1
    • B2k+1−12^{k+1}-1
    • C2k2^{k}
    • D2k+1−22^{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 nn, let Sn=∑r=1n(2r−1)2S_n=\sum_{r=1}^{n}(2r-1)^2. A student is proving by induction that Sn=n(2n−1)(2n+1)3S_n=\frac{n(2n-1)(2n+1)}{3}.
    (a)
    Find the value of S3S_3.
    [1 mark]
    • A3535
    • B2525
    • C105105
    • D1414
    (b)
    Assume the result is true for n=kn=k. Which expression is Sk+1S_{k+1} before any simplification?
    [1 mark]
    • Ak(2k−1)(2k+1)3+(2k−1)2\frac{k(2k-1)(2k+1)}{3}+(2k-1)^2
    • Bk(2k−1)(2k+1)3+(2k+2)2\frac{k(2k-1)(2k+1)}{3}+(2k+2)^2
    • Ck(2k−1)(2k+1)3+(2k+1)2\frac{k(2k-1)(2k+1)}{3}+(2k+1)^2
    • D(k+1)(2k+1)(2k+3)3+(2k+1)2\frac{(k+1)(2k+1)(2k+3)}{3}+(2k+1)^2
    (c)
    Show that k(2k−1)(2k+1)3+(2k+1)2=(k+1)(2k+1)(2k+3)3\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)=2n+2+32n+1f(n)=2^{n+2}+3^{2n+1}, where nn is a positive integer. It is to be proved by induction that f(n)f(n) is divisible by 77.
    (a)
    Show that f(k+1)−2f(k)=7×32k+1f(k+1)-2f(k)=7\times3^{2k+1}.
    [3 marks]
    (b)
    Hence prove by induction that f(n)f(n) is divisible by 77 for all positive integers nn.
    [4 marks]

    Total for question 7: 7 marks

  8. 8
    For positive integers nn, let Un=∑r=1nr(r+1)(r+2)U_n=\sum_{r=1}^{n}r(r+1)(r+2) and let Q=(32−10)\mathbf{Q}=\begin{pmatrix}3&2\\ -1&0\end{pmatrix}.
    (a)
    Prove by induction that Un=n(n+1)(n+2)(n+3)4U_n=\frac{n(n+1)(n+2)(n+3)}{4} for all positive integers nn.
    [6 marks]
    (b)
    Prove by induction that Qn=(2n+1−12n+1−21−2n2−2n)\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 nn.
    [6 marks]

    Total for question 8: 12 marks

End of questions

Topic tests