Proof by mathematical induction

Proof by mathematical induction Test

Spec 8.1 · Edexcel International 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

Edexcel International A Level Further Maths

Proof by mathematical induction

Total 27 marks

Name

Class

Date

  1. 1
    A student is proving by induction that ∑r=1nr=n(n+1)2\sum_{r=1}^{n}r=\frac{n(n+1)}{2} for all positive integers nn, and has already checked the case n=1n=1.
    (a)
    In the inductive step, the student assumes that the result is true for n=kn=k. What must the student then show?
    [1 mark]
    • AThat ∑r=1kr=k(k+1)2\sum_{r=1}^{k}r=\frac{k(k+1)}{2}
    • BThat the result is true for n=k+2n=k+2
    • CThat the result is true for all positive integers nn
    • DThat ∑r=1k+1r=(k+1)(k+2)2\sum_{r=1}^{k+1}r=\frac{(k+1)(k+2)}{2}
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    Which of these is a complete and correct conclusion to the proof?
    [1 mark]
    • AThe result is true for n=1n=1, so it is true for all positive integers nn.
    • BThe result is true for n=1n=1, and if it is true for n=kn=k then it is true for n=k+1n=k+1, so by mathematical induction it is true for all positive integers nn.
    • CIf the result is true for n=kn=k then it is true for n=k+1n=k+1, so it is true for all positive integers nn.
    • DThe result is true for n=k+1n=k+1, so it is true for all positive integers nn.
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Assuming the result is true for n=kn=k, show that it is true for n=k+1n=k+1.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: ∑r=1k+1r=k(k+1)2+(k+1)\sum_{r=1}^{k+1}r=\frac{k(k+1)}{2}+(k+1)
    A1:
    =(k+1)(k+2)2=(k+1)((k+1)+1)2=\frac{(k+1)(k+2)}{2}=\frac{(k+1)((k+1)+1)}{2}, the given form with n=k+1n=k+1

    Total for question 1: 4 marks

  2. 2
    Let f(n)=7n−1f(n)=7^n-1 for positive integers nn.
    (a)
    Find f(2)f(2).
    [1 mark]
    • A4848
    • B1313
    • C5050
    • D3636
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Find f(k+1)−f(k)f(k+1)-f(k).
    [1 mark]
    • A7k7^k
    • B6×7k+16\times7^{k+1}
    • C6×7k6\times7^k
    • D7k+1−17^{k+1}-1
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    Hence, or otherwise, show that if f(k)f(k) is divisible by 66 then f(k+1)f(k+1) is divisible by 66.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: f(k+1)=f(k)+6×7kf(k+1)=f(k)+6\times7^k, or f(k+1)=7f(k)+6f(k+1)=7f(k)+6
    A1: both terms are multiples of
    66 (using the assumption), so f(k+1)f(k+1) is divisible by 66

    Total for question 2: 4 marks

  3. 3
    A sequence is defined by u1=2u_1=2 and un+1=2un+3u_{n+1}=2u_n+3 for n≥1n\ge1.
    (a)
    Find u2u_2, u3u_3 and u4u_4, and verify that the formula un=5×2n−1−3u_n=5\times2^{n-1}-3 gives the correct values for n=1,2,3,4n=1,2,3,4.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: u2=2(2)+3u_2=2(2)+3 (uses the recurrence)
    A1:
    u2=7u_2=7, u3=17u_3=17, u4=37u_4=37
    A1: the formula gives
    2,7,17,372,7,17,37 for n=1,2,3,4n=1,2,3,4 (e.g. 5×23−3=375\times2^3-3=37)
    (b)
    Prove by induction that un=5×2n−1−3u_n=5\times2^{n-1}-3 for all positive integers nn.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: n=1n=1: 5×20−3=2=u15\times2^0-3=2=u_1, so the result is true for n=1n=1
    M1: assumes
    uk=5×2k−1−3u_k=5\times2^{k-1}-3 and uses uk+1=2uk+3=2(5×2k−1−3)+3u_{k+1}=2u_k+3=2\left(5\times2^{k-1}-3\right)+3
    A1:
    =5×2k−6+3=5×2k−3=5×2(k+1)−1−3=5\times2^k-6+3=5\times2^k-3=5\times2^{(k+1)-1}-3
    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

    Total for question 3: 7 marks

  4. 4
    Let M=(3−41−1)\mathbf{M}=\begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}.
    (a)
    Prove by induction that Mn=(2n+1−4nn1−2n)\mathbf{M}^n=\begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix} for all positive integers nn.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: n=1n=1: the formula gives (3−41−1)=M\begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}=\mathbf{M}
    M1: assumes true for
    n=kn=k and forms Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}
    A1: top row
    (3(2k+1)−4k, −4(2k+1)+4k)=(2k+3, −4k−4)\left(3(2k+1)-4k,\ -4(2k+1)+4k\right)=(2k+3,\ -4k-4)
    A1: bottom row
    (3k+1−2k, −4k−(1−2k))=(k+1, −2k−1)\left(3k+1-2k,\ -4k-(1-2k)\right)=(k+1,\ -2k-1)
    A1:
    (2(k+1)+1−4(k+1)k+11−2(k+1))\begin{pmatrix} 2(k+1)+1 & -4(k+1) \\ k+1 & 1-2(k+1) \end{pmatrix}, the formula with n=k+1n=k+1
    R1: 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
    (b)
    Use the result of part (a) to:
    (i) write down
    M12\mathbf{M}^{12};
    (ii) show that
    det⁡(Mn)=1\det\left(\mathbf{M}^n\right)=1 for all positive integers nn;
    (iii) hence write down
    (Mn)−1\left(\mathbf{M}^n\right)^{-1}.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) substitutes n=12n=12
    A1: (i)
    (25−4812−23)\begin{pmatrix} 25 & -48 \\ 12 & -23 \end{pmatrix}
    M1: (ii)
    (2n+1)(1−2n)−(−4n)(n)(2n+1)(1-2n)-(-4n)(n)
    A1: (ii)
    1−4n2+4n2=11-4n^2+4n^2=1
    M1: (iii) swaps the leading diagonal, negates the other entries and divides by
    11
    A1: (iii)
    (1−2n4n−n2n+1)\begin{pmatrix} 1-2n & 4n \\ -n & 2n+1 \end{pmatrix}

    Total for question 4: 12 marks

End of questions

Subtopic tests