Proof by mathematical induction

Proof by mathematical induction Test

Spec 1.1 · Edexcel 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 A-Level Further Maths

Proof by mathematical induction

Total 27 marks

Name

Class

Date

  1. 1
    Proof by mathematical induction is used to show that ∑r=1n1r(r+1)=nn+1\sum_{r=1}^{n}\frac{1}{r(r+1)}=\frac{n}{n+1} for all positive integers nn.
    (a)
    What is the value of each side of the identity when n=1n=1?
    [1 mark]
    • A11
    • B12\frac12
    • C13\frac13
    • D22
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Assuming the result is true for n=kn=k, which expression is equal to the sum of the first k+1k+1 terms?
    [1 mark]
    • Akk+1+1k(k+1)\frac{k}{k+1}+\frac{1}{k(k+1)}
    • Bk+1k+2+1(k+1)(k+2)\frac{k+1}{k+2}+\frac{1}{(k+1)(k+2)}
    • Ckk+1+1(k+1)(k+2)\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}
    • Dkk+1+1k+2\frac{k}{k+1}+\frac{1}{k+2}
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    Show that if the result is true for n=kn=k then it is true for n=k+1n=k+1.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: common denominator, e.g. k(k+2)+1(k+1)(k+2)\frac{k(k+2)+1}{(k+1)(k+2)} or k(k+2)(k+1)(k+2)+1(k+1)(k+2)\frac{k(k+2)}{(k+1)(k+2)}+\frac{1}{(k+1)(k+2)}
    A1:
    (k+1)2(k+1)(k+2)=k+1k+2\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}, which is the formula with n=k+1n=k+1
    Accept: a stated target of
    k+1(k+1)+1\frac{k+1}{(k+1)+1}

    Total for question 1: 4 marks

  2. 2
    Let f(n)=7n+5\mathrm{f}(n)=7^n+5, where nn is a positive integer.
    (a)
    Find f(2)\mathrm{f}(2).
    [1 mark]
    • A5454
    • B1919
    • C2424
    • D4949
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Which expression is equal to f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k)?
    [1 mark]
    • A7k7^k
    • B8×7k8\times7^k
    • C7k+1+57^{k+1}+5
    • D6×7k6\times7^k
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Given that f(k)\mathrm{f}(k) is divisible by 6 for some positive integer kk, show that f(k+1)\mathrm{f}(k+1) is also divisible by 6.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: f(k+1)=7⋅7k+5\mathrm{f}(k+1)=7\cdot7^k+5 with 7k=6m−57^k=6m-5 substituted (or f(k+1)−f(k)=6×7k\mathrm{f}(k+1)-\mathrm{f}(k)=6\times7^k)
    A1:
    f(k+1)=42m−30=6(7m−5)\mathrm{f}(k+1)=42m-30=6(7m-5), or f(k+1)=f(k)+6×7k\mathrm{f}(k+1)=\mathrm{f}(k)+6\times7^k, a multiple of 6 with a statement saying so

    Total for question 2: 4 marks

  3. 3
    The matrix A=(2101)\mathbf{A}=\begin{pmatrix}2&1\\0&1\end{pmatrix}.
    (a)
    Find A2\mathbf{A}^2 and A3\mathbf{A}^3, and hence suggest a formula for An\mathbf{A}^n.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: attempt at A2\mathbf{A}^2, giving (4301)\begin{pmatrix}4&3\\0&1\end{pmatrix}
    A1:
    A3=(8701)\mathbf{A}^3=\begin{pmatrix}8&7\\0&1\end{pmatrix}
    B1:
    An=(2n2n−101)\mathbf{A}^n=\begin{pmatrix}2^n&2^n-1\\0&1\end{pmatrix}
    Accept: the formula written in any equivalent form
    (b)
    Prove by induction that your formula for An\mathbf{A}^n is correct for all positive integers nn.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: true for n=1n=1: (2121−101)=(2101)=A\begin{pmatrix}2^1&2^1-1\\0&1\end{pmatrix}=\begin{pmatrix}2&1\\0&1\end{pmatrix}=\mathbf{A}
    M1: assume true for
    n=kn=k and form Ak+1=AkA\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A} (or AAk\mathbf{A}\mathbf{A}^k)
    A1:
    (2k+12k+2k−101)=(2k+12k+1−101)\begin{pmatrix}2^{k+1}&2^k+2^k-1\\0&1\end{pmatrix}=\begin{pmatrix}2^{k+1}&2^{k+1}-1\\0&1\end{pmatrix}
    A1: conclusion: true for
    n=1n=1, and if true for n=kn=k then true for n=k+1n=k+1, so true for all positive integers nn
    Accept: either order of multiplication

    Total for question 3: 7 marks

  4. 4
    In this question you must use proof by mathematical induction, stating the assumption made at the inductive step and ending with a clear conclusion. nn is a positive integer.
    (a)
    Prove that ∑r=1nr(r+2)=n(n+1)(2n+7)6\sum_{r=1}^{n}r(r+2)=\frac{n(n+1)(2n+7)}{6}.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: n=1n=1: LHS =3=3 and RHS =1×2×96=3=\frac{1\times2\times9}{6}=3
    M1: assume true for
    n=kn=k and add the (k+1)(k+1)th term, k(k+1)(2k+7)6+(k+1)(k+3)\frac{k(k+1)(2k+7)}{6}+(k+1)(k+3)
    M1: factor out
    k+16\frac{k+1}{6}, giving k+16[k(2k+7)+6(k+3)]\frac{k+1}{6}\left[k(2k+7)+6(k+3)\right]
    A1:
    (k+1)(2k2+13k+18)6\frac{(k+1)(2k^2+13k+18)}{6}
    A1:
    (k+1)(k+2)(2k+9)6\frac{(k+1)(k+2)(2k+9)}{6}, which is the formula with n=k+1n=k+1
    A1: conclusion: true for
    n=1n=1, and if true for n=kn=k then true for n=k+1n=k+1, so true for all positive integers nn
    (b)
    Prove that 2n+2+32n+12^{n+2}+3^{2n+1} is divisible by 7.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: n=1n=1: 23+33=35=7×52^3+3^3=35=7\times5, divisible by 7
    M1: assume
    f(k)=2k+2+32k+1\mathrm{f}(k)=2^{k+2}+3^{2k+1} is divisible by 7, e.g. =7m=7m
    M1:
    f(k+1)=2k+3+32k+3=2⋅2k+2+9⋅32k+1\mathrm{f}(k+1)=2^{k+3}+3^{2k+3}=2\cdot2^{k+2}+9\cdot3^{2k+1}
    A1:
    f(k+1)−2f(k)=7⋅32k+1\mathrm{f}(k+1)-2\mathrm{f}(k)=7\cdot3^{2k+1}, or f(k+1)=2(7m−32k+1)+9⋅32k+1\mathrm{f}(k+1)=2(7m-3^{2k+1})+9\cdot3^{2k+1}
    A1:
    f(k+1)=14m+7⋅32k+1=7(2m+32k+1)\mathrm{f}(k+1)=14m+7\cdot3^{2k+1}=7(2m+3^{2k+1}), a multiple of 7
    A1: conclusion: true for
    n=1n=1, and if true for n=kn=k then true for n=k+1n=k+1, so true for all positive integers nn
    Accept: other valid combinations, e.g.
    f(k+1)−9f(k)=−7⋅2k+2\mathrm{f}(k+1)-9\mathrm{f}(k)=-7\cdot2^{k+2}

    Total for question 4: 12 marks

End of questions

Subtopic tests