Hard Further Maths Proof by induction Questions

Challenging, exam-style Further Maths Proof by induction questions with worked solutions. Stretch yourself on the hardest series-step, induction, inductive-step, series-target problems.

series-stepinductioninductive-stepseries-targetdivis-stepdivisibility
Further Maths34 questionsStep-by-step solutions
Question 1
8 markschallenging
The matrix M=(3103)M=\begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}. Which of the following is M5M^{5}?
Show worked solution

Worked solution

  1. Recall the induction result for MnM^{n}

    Mn=(3n3n−1n03n)M^{n}=\begin{pmatrix} 3^{n} & 3^{n - 1} n \\ 0 & 3^{n} \end{pmatrix}

    Induction establishes a formula for every power.

  2. Substitute n=5n=5

    M5=(2434050243)M^{5}=\begin{pmatrix} 243 & 405 \\ 0 & 243 \end{pmatrix}

    Evaluate each entry at the required power.

  3. State the proposition to be proved

    P(n): Mn=(3n3n−1n03n)P(n):\ M^{n}=\begin{pmatrix} 3^{n} & 3^{n - 1} n \\ 0 & 3^{n} \end{pmatrix}

    Name the statement about the nnth power of the matrix.

  4. Test the base case n=1n=1

    M1=(3103)M^{1}=\begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}

    The first power is just the matrix itself.

  5. Substitute n=1n=1 into the proposed formula

    (3n3n−1n03n)∣n=1=(3103)\begin{pmatrix} 3^{n} & 3^{n - 1} n \\ 0 & 3^{n} \end{pmatrix}\Big|_{n=1}=\begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}

    The formula reproduces MM, so the base case holds.

  6. State the inductive hypothesis

    Assume Mk=(3k3k−1k03k)\text{Assume } M^{k}=\begin{pmatrix} 3^{k} & 3^{k - 1} k \\ 0 & 3^{k} \end{pmatrix}

    Assume the formula is correct for some positive integer kk.

  7. Use the power law for matrices

    Mk+1=MkMM^{k+1}=M^{k}M

    One extra factor of MM takes the kkth power to the (k+1)(k+1)th.

  8. Substitute the inductive hypothesis

    Mk+1=(3k3k−1k03k)(3103)M^{k+1}=\begin{pmatrix} 3^{k} & 3^{k - 1} k \\ 0 & 3^{k} \end{pmatrix}\begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix}

    Replace MkM^{k} by the assumed formula.

  9. Multiply the two matrices

    Mk+1=(3⋅3k3kk+3k03⋅3k)M^{k+1}=\begin{pmatrix} 3 \cdot 3^{k} & 3^{k} k + 3^{k} \\ 0 & 3 \cdot 3^{k} \end{pmatrix}

    Multiply row by column and simplify each entry.

  10. Write the target formula at n=k+1n=k+1

    Target=(3⋅3k3kk+3k03⋅3k)\text{Target}=\begin{pmatrix} 3 \cdot 3^{k} & 3^{k} k + 3^{k} \\ 0 & 3 \cdot 3^{k} \end{pmatrix}

    Replace nn by k+1k+1 in the proposed formula.

  11. Compare the product with the target

    (3⋅3k3kk+3k03⋅3k)=(3⋅3k3kk+3k03⋅3k)\begin{pmatrix} 3 \cdot 3^{k} & 3^{k} k + 3^{k} \\ 0 & 3 \cdot 3^{k} \end{pmatrix}=\begin{pmatrix} 3 \cdot 3^{k} & 3^{k} k + 3^{k} \\ 0 & 3 \cdot 3^{k} \end{pmatrix}

    Every entry agrees, so the inductive step is complete.

  12. Deduce the inductive step

    P(k)⇒P(k+1)P(k)\Rightarrow P(k+1)

    Truth at n=kn=k forces truth at n=k+1n=k+1.

  13. Combine the base case and the inductive step

    P(1) true and P(k)⇒P(k+1)P(1)\ \text{true and}\ P(k)\Rightarrow P(k+1)

    Both requirements of induction are satisfied.

  14. State the conclusion of the induction

    Mn=(3n3n−1n03n)∀n∈Z+M^{n}=\begin{pmatrix} 3^{n} & 3^{n - 1} n \\ 0 & 3^{n} \end{pmatrix}\quad \forall n\in\mathbb{Z}^{+}

    The formula holds for every positive integer power.

  15. Recall the structure of a proof by induction

    P(1) true,P(k)⇒P(k+1)P(1)\ \text{true},\quad P(k)\Rightarrow P(k+1)

    A proof by induction needs a base case and an inductive step.

  16. Select the matching matrix

    (2434050243)\begin{pmatrix} 243 & 405 \\ 0 & 243 \end{pmatrix}

    This is M5M^{5}.

Answer
(2434050243)\begin{pmatrix} 243 & 405 \\ 0 & 243 \end{pmatrix}
Question 2
8 markschallenging
The matrix M=(4011)M=\begin{pmatrix} 4 & 0 \\ 1 & 1 \end{pmatrix} and it is assumed that Mk=(4k04k3−131)M^{k}=\begin{pmatrix} 4^{k} & 0 \\ \frac{4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}. Which of the following is Mk+1M^{k+1}?
Show worked solution

Worked solution

  1. Use the power law for matrices

    Mk+1=MkMM^{k+1}=M^{k}M

    Multiply the assumed kkth power by one more factor of MM.

  2. Carry out the multiplication

    Mk+1=(4k04k3−131)(4011)=(4⋅4k04⋅4k3−131)M^{k+1}=\begin{pmatrix} 4^{k} & 0 \\ \frac{4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}\begin{pmatrix} 4 & 0 \\ 1 & 1 \end{pmatrix}=\begin{pmatrix} 4 \cdot 4^{k} & 0 \\ \frac{4 \cdot 4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Each entry is a row-times-column product.

  3. State the proposition to be proved

    P(n): Mn=(4n04n3−131)P(n):\ M^{n}=\begin{pmatrix} 4^{n} & 0 \\ \frac{4^{n}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Name the statement about the nnth power of the matrix.

  4. Test the base case n=1n=1

    M1=(4011)M^{1}=\begin{pmatrix} 4 & 0 \\ 1 & 1 \end{pmatrix}

    The first power is just the matrix itself.

  5. Substitute n=1n=1 into the proposed formula

    (4n04n3−131)∣n=1=(4011)\begin{pmatrix} 4^{n} & 0 \\ \frac{4^{n}}{3} - \frac{1}{3} & 1 \end{pmatrix}\Big|_{n=1}=\begin{pmatrix} 4 & 0 \\ 1 & 1 \end{pmatrix}

    The formula reproduces MM, so the base case holds.

  6. State the inductive hypothesis

    Assume Mk=(4k04k3−131)\text{Assume } M^{k}=\begin{pmatrix} 4^{k} & 0 \\ \frac{4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Assume the formula is correct for some positive integer kk.

  7. Use the power law for matrices

    Mk+1=MkMM^{k+1}=M^{k}M

    One extra factor of MM takes the kkth power to the (k+1)(k+1)th.

  8. Substitute the inductive hypothesis

    Mk+1=(4k04k3−131)(4011)M^{k+1}=\begin{pmatrix} 4^{k} & 0 \\ \frac{4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}\begin{pmatrix} 4 & 0 \\ 1 & 1 \end{pmatrix}

    Replace MkM^{k} by the assumed formula.

  9. Multiply the two matrices

    Mk+1=(4⋅4k04⋅4k3−131)M^{k+1}=\begin{pmatrix} 4 \cdot 4^{k} & 0 \\ \frac{4 \cdot 4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Multiply row by column and simplify each entry.

  10. Write the target formula at n=k+1n=k+1

    Target=(4⋅4k04⋅4k3−131)\text{Target}=\begin{pmatrix} 4 \cdot 4^{k} & 0 \\ \frac{4 \cdot 4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Replace nn by k+1k+1 in the proposed formula.

  11. Compare the product with the target

    (4⋅4k04⋅4k3−131)=(4⋅4k04⋅4k3−131)\begin{pmatrix} 4 \cdot 4^{k} & 0 \\ \frac{4 \cdot 4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}=\begin{pmatrix} 4 \cdot 4^{k} & 0 \\ \frac{4 \cdot 4^{k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    Every entry agrees, so the inductive step is complete.

  12. Deduce the inductive step

    P(k)⇒P(k+1)P(k)\Rightarrow P(k+1)

    Truth at n=kn=k forces truth at n=k+1n=k+1.

  13. Combine the base case and the inductive step

    P(1) true and P(k)⇒P(k+1)P(1)\ \text{true and}\ P(k)\Rightarrow P(k+1)

    Both requirements of induction are satisfied.

  14. State the conclusion of the induction

    Mn=(4n04n3−131)∀n∈Z+M^{n}=\begin{pmatrix} 4^{n} & 0 \\ \frac{4^{n}}{3} - \frac{1}{3} & 1 \end{pmatrix}\quad \forall n\in\mathbb{Z}^{+}

    The formula holds for every positive integer power.

  15. Recall the structure of a proof by induction

    P(1) true,P(k)⇒P(k+1)P(1)\ \text{true},\quad P(k)\Rightarrow P(k+1)

    A proof by induction needs a base case and an inductive step.

  16. Select the correct (k+1)(k+1)th power

    (22k+204⋅22k3−131)\begin{pmatrix} 2^{2 k + 2} & 0 \\ \frac{4 \cdot 2^{2 k}}{3} - \frac{1}{3} & 1 \end{pmatrix}

    This matrix is MkMM^{k}M.

Answer
(22k+204⋅22k3−131)\begin{pmatrix} 2^{2 k + 2} & 0 \\ \frac{4 \cdot 2^{2 k}}{3} - \frac{1}{3} & 1 \end{pmatrix}
Question 3
8 markschallenging
Induction proves that ∑r=1n[r(r+3)]=n(n+1)(n+5)3\sum_{r=1}^{n}\left[r (r + 3)\right]=\frac{n (n + 1) (n + 5)}{3}. Which of the following is the value of ∑r=112[r(r+3)]\sum_{r=1}^{12}\left[r (r + 3)\right]?
Show worked solution

Worked solution

  1. Quote the proved closed form

    ∑r=1n[r(r+3)]=n(n+1)(n+5)3\sum_{r=1}^{n}\left[r (r + 3)\right]=\frac{n (n + 1) (n + 5)}{3}

    The formula has been established by induction.

  2. Substitute n=12n=12

    n=12:n(n+1)(n+5)3=884n=12:\quad \frac{n (n + 1) (n + 5)}{3}=884

    Evaluate the closed form at the required upper limit.

  3. State the proposition to be proved

    P(n): ∑r=1n[r(r+3)]=n(n+1)(n+5)3P(n):\ \sum_{r=1}^{n}\left[r (r + 3)\right]=\frac{n (n + 1) (n + 5)}{3}

    Name the statement so the base case and inductive step can refer to it.

  4. Evaluate the left-hand side for the base case

    n=1:LHS=4n=1:\quad \text{LHS}=4

    Substitute n=1n=1 into the summation.

  5. Evaluate the right-hand side for the base case

    n=1:RHS=4n=1:\quad \text{RHS}=4

    Substitute n=1n=1 into the closed form.

  6. Conclude the base case is true

    LHS=RHS=4 ⇒ P(1) true\text{LHS}=\text{RHS}=4\ \Rightarrow\ P(1)\ \text{true}

    Both sides agree, so the statement holds when n=1n=1.

  7. State the inductive hypothesis

    Assume ∑r=1k[r(r+3)]=k(k+1)(k+5)3\text{Assume } \sum_{r=1}^{k}\left[r (r + 3)\right]=\frac{k (k + 1) (k + 5)}{3}

    Assume the result is true for some positive integer kk.

  8. Split the sum to k+1k+1 at its last term

    ∑r=1k+1[r(r+3)]=∑r=1k[r(r+3)]+(k+1)(k+4)\sum_{r=1}^{k+1}\left[r (r + 3)\right]=\sum_{r=1}^{k}\left[r (r + 3)\right]+(k + 1) (k + 4)

    The sum to k+1k+1 is the sum to kk plus the (k+1)(k+1)th term.

  9. Substitute the inductive hypothesis

    ∑r=1k+1[r(r+3)]=k(k+1)(k+5)3+(k+1)(k+4)\sum_{r=1}^{k+1}\left[r (r + 3)\right]=\frac{k (k + 1) (k + 5)}{3}+(k + 1) (k + 4)

    Replace the sum to kk using the assumed result.

  10. Write the added term explicitly

    uk+1=(k+1)(k+4)=k2+5k+4u_{k+1}=(k + 1) (k + 4)=k^{2} + 5 k + 4

    Expand the (k+1)(k+1)th term of the series.

  11. Combine the two parts over a common denominator

    =(k3+13)(k(k+5)+3k+12)=(\frac{k}{3} + \frac{1}{3}) (k (k + 5) + 3 k + 12)

    Put the assumed sum and the new term over one denominator.

  12. Simplify the combined expression

    =k33+3k2+20k3+4=\frac{k^{3}}{3} + 3 k^{2} + \frac{20 k}{3} + 4

    Expand and collect like terms.

  13. Factorise the simplified expression

    =(k+1)(k+2)(k+6)3=\frac{(k + 1) (k + 2) (k + 6)}{3}

    Factorising reveals the target structure.

  14. Write down the target right-hand side at n=k+1n=k+1

    Target=(k+1)(k+2)(k+6)3=k33+3k2+20k3+4\text{Target}=\frac{(k + 1) (k + 2) (k + 6)}{3}=\frac{k^{3}}{3} + 3 k^{2} + \frac{20 k}{3} + 4

    This is what the closed form becomes when nn is replaced by k+1k+1.

  15. Compare the two expressions

    k33+3k2+20k3+4=k33+3k2+20k3+4\frac{k^{3}}{3} + 3 k^{2} + \frac{20 k}{3} + 4=\frac{k^{3}}{3} + 3 k^{2} + \frac{20 k}{3} + 4

    The expression obtained matches the target exactly.

  16. Select the value of the sum

    884884

    This is the value of the series.

Answer
884884
Question 4
8 markschallenging
Let f(n)=26n+32n−2f(n)=2^{6 n} + 3^{2 n - 2}, where nn is a positive integer. Which of the following integers divides f(n)f(n) for every positive integer nn?
Show worked solution

Worked solution

  1. Evaluate the first two values of ff

    f(1)=65,f(2)=4105f(1)=65,\quad f(2)=4105

    Small values quickly rule out most candidates.

  2. Find the common factor of these values

    gcd⁡(65, 4105)=5\gcd\left(65,\ 4105\right)=5

    The divisor must divide every value of ff.

  3. State the proposition to be proved

    P(n): 26n+32n−2 is divisible by 5P(n):\ 2^{6 n} + 3^{2 n - 2}\ \text{is divisible by } 5

    Name the divisibility statement.

  4. Test the base case n=1n=1

    f(1)=65f(1)=65

    Substitute n=1n=1 into f(n)f(n).

  5. Confirm the base case is divisible

    65=5×1365=5\times 13

    The base value is a whole-number multiple of the divisor.

  6. State the inductive hypothesis

    f(k)=26k+32k−2=5m,m∈Zf(k)=2^{6 k} + 3^{2 k - 2}=5 m,\quad m\in\mathbb{Z}

    Assume f(k)f(k) is divisible by dd for some positive integer kk.

  7. Write down f(k+1)f(k+1)

    f(k+1)=26k+6+32kf(k+1)=2^{6 k + 6} + 3^{2 k}

    Replace nn by k+1k+1 in f(n)f(n).

  8. Form the combination f(k+1)−64f(k)f(k+1)-64f(k)

    f(k+1)−64f(k)=(26k+6+32k)−64(26k+32k−2)f(k+1)-64f(k)=\left(2^{6 k + 6} + 3^{2 k}\right)-64\left(2^{6 k} + 3^{2 k - 2}\right)

    Subtracting a multiple of f(k)f(k) removes the awkward exponential term.

  9. Expand using index laws

    f(k+1)=64⋅26k+32kf(k+1)=64 \cdot 2^{6 k} + 3^{2 k}

    Peel one factor off each power so the kk case appears.

  10. Simplify the combination

    f(k+1)−64f(k)=−55⋅32k−2f(k+1)-64f(k)=- 55 \cdot 3^{2 k - 2}

    The remaining expression is the key to the proof.

  11. Show the remainder term is a multiple of 55

    −55⋅32k−2=5(−11⋅32k−2)- 55 \cdot 3^{2 k - 2}=5\left(- 11 \cdot 3^{2 k - 2}\right)

    The leftover term factorises with dd as a factor.

  12. Rearrange to express f(k+1)f(k+1)

    f(k+1)=64f(k)−55⋅32k−2f(k+1)=64f(k)- 55 \cdot 3^{2 k - 2}

    Make f(k+1)f(k+1) the subject.

  13. Substitute the inductive hypothesis f(k)=5mf(k)=5m

    f(k+1)=−55⋅32k−2+320mf(k+1)=- 55 \cdot 3^{2 k - 2} + 320 m

    Use the assumption that f(k)f(k) is dd times an integer.

  14. Factor out the divisor

    f(k+1)=5(−11⋅32k−2+64m)f(k+1)=5\left(- 11 \cdot 3^{2 k - 2} + 64 m\right)

    Both terms carry a factor of dd.

  15. Conclude f(k+1)f(k+1) is divisible by 55

    5∣f(k+1)5\mid f(k+1)

    The bracket is an integer, so f(k+1)f(k+1) is a multiple of dd.

  16. Select the divisor proved by induction

    55

    Induction confirms this divides f(n)f(n) for every nn.

Answer
55
Question 5
8 markschallenging
Let f(n)=n3+6n2+8nf(n)=n^{3} + 6 n^{2} + 8 n, which induction shows is divisible by 33 for all positive integers nn. Which of the following is f(k+1)−f(k)f(k+1)-f(k) in its simplest form?
Show worked solution

Worked solution

  1. Write down f(k+1)f(k+1)

    f(k+1)=8k+(k+1)3+6(k+1)2+8f(k+1)=8 k + (k + 1)^{3} + 6 (k + 1)^{2} + 8

    Substitute n=k+1n=k+1 into f(n)f(n).

  2. Subtract f(k)f(k) and simplify

    f(k+1)−f(k)=3k2+15k+15f(k+1)-f(k)=3 k^{2} + 15 k + 15

    The leading exponential terms cancel.

  3. State the proposition to be proved

    P(n): n3+6n2+8n is divisible by 3P(n):\ n^{3} + 6 n^{2} + 8 n\ \text{is divisible by } 3

    Name the divisibility statement.

  4. Test the base case n=1n=1

    f(1)=15f(1)=15

    Substitute n=1n=1 into f(n)f(n).

  5. Confirm the base case is divisible

    15=3×515=3\times 5

    The base value is a whole-number multiple of the divisor.

  6. State the inductive hypothesis

    f(k)=k3+6k2+8k=3m,m∈Zf(k)=k^{3} + 6 k^{2} + 8 k=3 m,\quad m\in\mathbb{Z}

    Assume f(k)f(k) is divisible by dd for some positive integer kk.

  7. Write down f(k+1)f(k+1)

    f(k+1)=8k+(k+1)3+6(k+1)2+8f(k+1)=8 k + (k + 1)^{3} + 6 (k + 1)^{2} + 8

    Replace nn by k+1k+1 in f(n)f(n).

  8. Form the combination f(k+1)−f(k)f(k+1)-f(k)

    f(k+1)−f(k)=(8k+(k+1)3+6(k+1)2+8)−(k3+6k2+8k)f(k+1)-f(k)=\left(8 k + (k + 1)^{3} + 6 (k + 1)^{2} + 8\right)-\left(k^{3} + 6 k^{2} + 8 k\right)

    Subtracting a multiple of f(k)f(k) removes the awkward exponential term.

  9. Expand using index laws

    f(k+1)=k3+9k2+23k+15f(k+1)=k^{3} + 9 k^{2} + 23 k + 15

    Peel one factor off each power so the kk case appears.

  10. Simplify the combination

    f(k+1)−f(k)=3k2+15k+15f(k+1)-f(k)=3 k^{2} + 15 k + 15

    The remaining expression is the key to the proof.

  11. Show the remainder term is a multiple of 33

    3k2+15k+15=3(k2+5k+5)3 k^{2} + 15 k + 15=3\left(k^{2} + 5 k + 5\right)

    The leftover term factorises with dd as a factor.

  12. Rearrange to express f(k+1)f(k+1)

    f(k+1)=f(k)+3k2+15k+15f(k+1)=f(k)+3 k^{2} + 15 k + 15

    Make f(k+1)f(k+1) the subject.

  13. Substitute the inductive hypothesis f(k)=3mf(k)=3m

    f(k+1)=3k2+15k+3m+15f(k+1)=3 k^{2} + 15 k + 3 m + 15

    Use the assumption that f(k)f(k) is dd times an integer.

  14. Factor out the divisor

    f(k+1)=3(k2+5k+m+5)f(k+1)=3\left(k^{2} + 5 k + m + 5\right)

    Both terms carry a factor of dd.

  15. Conclude f(k+1)f(k+1) is divisible by 33

    3∣f(k+1)3\mid f(k+1)

    The bracket is an integer, so f(k+1)f(k+1) is a multiple of dd.

  16. Select the simplified combination

    3k2+15k+153 k^{2} + 15 k + 15

    This expression is a multiple of 33.

Answer
3k2+15k+153 k^{2} + 15 k + 15

Unlock 29 more Proof by induction questions

Create a free account to work through every Further Maths Proof by induction question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Proof by induction practice

Practice QuestionsWorked Solutions

Related Pure Maths topics

Argand diagramsComplex numbers: arithmeticModelling with differential equationsComplex numbers: de MoivreFirst-order differential equationsFurther calculus