Induction for divisibility and matrix powers

Induction for divisibility and matrix powers Test

Spec A1 · AQA A-Level Further Maths: Subtopic test

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 10 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.

10 questions, 27 marks

AQA A-Level Further Maths

Induction for divisibility and matrix powers

Total 27 marks

Name

Class

Date

  1. 1
    Let f(n)=5n+3f(n)=5^n+3 for positive integers nn. It is to be proved by induction that f(n)f(n) is divisible by 44 for all nn.
    (a)
    Find the value of f(3)f(3).
    [1 mark]
    • A128128
    • B1818
    • C125125
    • D512512
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Which statement is the correct inductive hypothesis?
    [1 mark]
    • A5k+1+35^{k+1}+3 is divisible by 44
    • B5k+3=45^k+3=4
    • C5k+3=4k5^k+3=4k
    • D5k+3=4m5^k+3=4m for some integer mm
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Assuming that f(k)f(k) is divisible by 44, show that f(k+1)f(k+1) is divisible by 44.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: f(k+1)−f(k)=5k+1−5k=4×5kf(k+1)-f(k)=5^{k+1}-5^k=4\times5^k, or f(k+1)=5(4m−3)+3f(k+1)=5\left(4m-3\right)+3 using 5k+3=4m5^k+3=4m
    A1:
    f(k+1)=4m+4×5k=4(m+5k)f(k+1)=4m+4\times5^k=4\left(m+5^k\right), or 20m−12=4(5m−3)20m-12=4(5m-3), a multiple of 44
    Accept: any correct argument that
    f(k+1)f(k+1) is an integer multiple of 44

    Total for question 1: 4 marks

  2. 2
    The matrix M=(1201)\mathbf{M}=\begin{pmatrix}1&2\\ 0&1\end{pmatrix} satisfies Mn=(12n01)\mathbf{M}^n=\begin{pmatrix}1&2n\\ 0&1\end{pmatrix} for every positive integer nn.
    (a)
    Find M3\mathbf{M}^3.
    [1 mark]
    • A(1801)\begin{pmatrix}1&8\\ 0&1\end{pmatrix}
    • B(1601)\begin{pmatrix}1&6\\ 0&1\end{pmatrix}
    • C(1201)\begin{pmatrix}1&2\\ 0&1\end{pmatrix}
    • D(1603)\begin{pmatrix}1&6\\ 0&3\end{pmatrix}
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    In an inductive proof of the formula, the hypothesis is assumed for n=kn=k. Which matrix is MkM\mathbf{M}^k\mathbf{M}?
    [1 mark]
    • A(14k01)\begin{pmatrix}1&4k\\ 0&1\end{pmatrix}
    • B(12k01)\begin{pmatrix}1&2k\\ 0&1\end{pmatrix}
    • C(12k+201)\begin{pmatrix}1&2k+2\\ 0&1\end{pmatrix}
    • D(12k+202)\begin{pmatrix}1&2k+2\\ 0&2\end{pmatrix}
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    Find the smallest positive integer nn for which the top-right entry of Mn\mathbf{M}^n is greater than 10001000.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: 2n>10002n>1000
    A1:
    n=501n=501
    Do not accept:
    n=500n=500, where the entry equals 10001000 rather than exceeding it

    Total for question 2: 4 marks

  3. 3
    Let A=(3−22−1)\mathbf{A}=\begin{pmatrix}3&-2\\ 2&-1\end{pmatrix}. A student conjectures that An=(1+2n−2n2n1−2n)\mathbf{A}^n=\begin{pmatrix}1+2n&-2n\\ 2n&1-2n\end{pmatrix} for all positive integers nn.
    (a)
    Calculate A2\mathbf{A}^2 and A3\mathbf{A}^3, and show that the conjecture is correct for n=2n=2 and n=3n=3.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: attempts A×A\mathbf{A}\times\mathbf{A} (or A2×A\mathbf{A}^2\times\mathbf{A} for the cube)
    A1:
    A2=(5−44−3)\mathbf{A}^2=\begin{pmatrix}5&-4\\ 4&-3\end{pmatrix}, matching the formula with n=2n=2
    A1:
    A3=(7−66−5)\mathbf{A}^3=\begin{pmatrix}7&-6\\ 6&-5\end{pmatrix}, matching the formula with n=3n=3
    (b)
    Prove by induction that the conjecture is true for all positive integers nn.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: n=1n=1: (1+2−221−2)=(3−22−1)=A\begin{pmatrix}1+2&-2\\ 2&1-2\end{pmatrix}=\begin{pmatrix}3&-2\\ 2&-1\end{pmatrix}=\mathbf{A}, so true for n=1n=1
    M1: assumes true for
    n=kn=k and forms Ak+1=AkA=(1+2k−2k2k1−2k)(3−22−1)\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}=\begin{pmatrix}1+2k&-2k\\ 2k&1-2k\end{pmatrix}\begin{pmatrix}3&-2\\ 2&-1\end{pmatrix}
    A1:
    =(3+2k−2k−22k+2−2k−1)=\begin{pmatrix}3+2k&-2k-2\\ 2k+2&-2k-1\end{pmatrix}, all four entries correct
    A1: this equals
    (1+2(k+1)−2(k+1)2(k+1)1−2(k+1))\begin{pmatrix}1+2(k+1)&-2(k+1)\\ 2(k+1)&1-2(k+1)\end{pmatrix}, the formula with n=k+1n=k+1; true for n=1n=1 and true for n=kn=k implies true for n=k+1n=k+1, so true for all positive integers nn by induction
    Accept:
    Ak+1=AAk\mathbf{A}^{k+1}=\mathbf{A}\mathbf{A}^k

    Total for question 3: 7 marks

  4. 4
    Let f(n)=32n+7f(n)=3^{2n}+7 and g(n)=n3+11ng(n)=n^3+11n, where nn is a positive integer.
    (a)
    Prove by induction that f(n)f(n) is divisible by 88 for all positive integers nn.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: f(1)=9+7=16=8×2f(1)=9+7=16=8\times2, so true for n=1n=1
    M1: assumes
    f(k)=32k+7=8mf(k)=3^{2k}+7=8m for some integer mm, and considers f(k+1)−f(k)f(k+1)-f(k) (or f(k+1)f(k+1))
    A1:
    f(k+1)−f(k)=32k+2−32k=8×32kf(k+1)-f(k)=3^{2k+2}-3^{2k}=8\times3^{2k}
    M1:
    f(k+1)=f(k)+8×32k=8m+8×32kf(k+1)=f(k)+8\times3^{2k}=8m+8\times3^{2k}
    A1:
    =8(m+32k)=8\left(m+3^{2k}\right), a multiple of 88
    A1: conclusion: true for
    n=1n=1, and true for n=kn=k implies true for n=k+1n=k+1, so true for all positive integers nn by induction
    (b)
    Prove by induction that g(n)g(n) is divisible by 66 for all positive integers nn.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: g(1)=1+11=12=6×2g(1)=1+11=12=6\times2, so true for n=1n=1
    M1: assumes
    g(k)=6mg(k)=6m for some integer mm and forms g(k+1)−g(k)=(k+1)3+11(k+1)−k3−11kg(k+1)-g(k)=(k+1)^3+11(k+1)-k^3-11k
    A1:
    =3k2+3k+12=3k(k+1)+12=3k^2+3k+12=3k(k+1)+12
    M1:
    k(k+1)k(k+1) is a product of consecutive integers so is even, k(k+1)=2jk(k+1)=2j, so 3k(k+1)=6j3k(k+1)=6j
    A1:
    g(k+1)=6m+6j+12=6(m+j+2)g(k+1)=6m+6j+12=6(m+j+2), a multiple of 66
    A1: conclusion: true for
    n=1n=1, and true for n=kn=k implies true for n=k+1n=k+1, so true for all positive integers nn by induction
    Accept: checking separately that
    3k(k+1)3k(k+1) is divisible by 66 for even and odd kk

    Total for question 4: 12 marks

End of questions

Subtopic tests