Home · A-Level Further Maths 9231 · Proof by induction · Proof by induction: divisibility, matrices and derivatives · Practice
AS & A Level · Practice questions · Proof by induction: divisibility, matrices and derivatives

Assume k, deliver k + 1.

Six original Cambridge-style questions on proof by induction beyond sums: divisibility, matrix powers and \(n\)th derivatives, including two where you find the formula first. Every solution is written as a model proof you can copy the shape of.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.
The method

Base case, assumption, step, conclusion.

01
Recall
[3 marks]

Prove by induction that \(9^{n} - 1\) is divisible by 8 for every positive integer \(n\).

  • Base case: \(n = 1\) gives \(9 - 1 = 8 = 8 \times 1\), so the result is true for \(n = 1\). ✓
  • Assume it is true for \(n = k\): \(9^{k} - 1 = 8m\) for some integer \(m\), so \(9^{k} = 8m + 1\). ✓
  • Then \(9^{k+1} - 1 = 9 \cdot 9^{k} - 1 = 9(8m + 1) - 1 = 72m + 8 = 8(9m + 1)\), a multiple of 8, so the result is true for \(n = k + 1\). ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, \(9^{n} - 1\) is divisible by 8 for every positive integer \(n\). ✓
02
Calculation
[4 marks]

Prove by induction that \(5^{n} - 4n - 1\) is divisible by 16 for every positive integer \(n\).

  • Let \(f(n) = 5^{n} - 4n - 1\). Base case: \(f(1) = 5 - 4 - 1 = 0 = 16 \times 0\), which is divisible by 16. ✓
  • Assume \(f(k) = 16m\) for some integer \(m\), for some positive integer \(k\). ✓
  • \(f(k + 1) - 5f(k) = 5^{k+1} - 4k - 5 - 5^{k+1} + 20k + 5 = 16k\). ✓
  • So \(f(k + 1) = 5f(k) + 16k = 80m + 16k = 16(5m + k)\), a multiple of 16. ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, \(f(n)\) is divisible by 16 for every positive integer \(n\). ✓
03
Proof
[5 marks]

Prove by mathematical induction that \(3^{2n} + 4 \times 7^{n} - 5\) is divisible by 8 for every positive integer \(n\).

  • Let \(f(n) = 3^{2n} + 4 \times 7^{n} - 5\). Base case: \(f(1) = 9 + 28 - 5 = 32 = 8 \times 4\), so the result is true for \(n = 1\). ✓
  • Assume \(f(k) = 8m\) for some integer \(m\), for some positive integer \(k\). ✓
  • \(f(k + 1) = 9 \cdot 3^{2k} + 28 \times 7^{k} - 5\), so \(f(k + 1) - 9f(k) = 28 \times 7^{k} - 36 \times 7^{k} - 5 + 45 = -8 \times 7^{k} + 40\). ✓
  • Hence \(f(k + 1) = 72m - 8 \times 7^{k} + 40 = 8\big(9m - 7^{k} + 5\big)\), and \(9m - 7^{k} + 5\) is an integer, so \(f(k + 1)\) is divisible by 8. ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, \(f(n)\) is divisible by 8 for every positive integer \(n\). ✓
04
Analysis
[6 marks]

The matrix \(\mathbf{M} = \begin{pmatrix} 4 & -3 \\ 3 & -2 \end{pmatrix}\).

(a) Find \(\mathbf{M}^{2}\) and \(\mathbf{M}^{3}\).

(b) Conjecture a formula for \(\mathbf{M}^{n}\), where \(n\) is a positive integer.

(c) Prove your conjecture by mathematical induction.

  • (a) \(\mathbf{M}^{2} = \begin{pmatrix} 7 & -6 \\ 6 & -5 \end{pmatrix}\), \(\mathbf{M}^{3} = \mathbf{M}^{2}\mathbf{M} = \begin{pmatrix} 10 & -9 \\ 9 & -8 \end{pmatrix}\). ✓
  • (b) The entries change by 3 each time: top left 4, 7, 10 is \(1 + 3n\), top right \(-3n\), bottom left \(3n\), bottom right \(-2, -5, -8\) is \(1 - 3n\). Conjecture \(\mathbf{M}^{n} = \begin{pmatrix} 1 + 3n & -3n \\ 3n & 1 - 3n \end{pmatrix}\). ✓
  • (c) Base case: \(n = 1\) gives \(\begin{pmatrix} 4 & -3 \\ 3 & -2 \end{pmatrix} = \mathbf{M}\). ✓
  • Assume \(\mathbf{M}^{k} = \begin{pmatrix} 1 + 3k & -3k \\ 3k & 1 - 3k \end{pmatrix}\) for some positive integer \(k\). Then \(\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M}\), which is \(\begin{pmatrix} 4 + 12k - 9k & -3 - 9k + 6k \\ 12k + 3 - 9k & -9k - 2 + 6k \end{pmatrix}\) ✓
  • \(= \begin{pmatrix} 4 + 3k & -3 - 3k \\ 3 + 3k & -2 - 3k \end{pmatrix}\), that is \(\begin{pmatrix} 1 + 3(k + 1) & -3(k + 1) \\ 3(k + 1) & 1 - 3(k + 1) \end{pmatrix}\), the formula for \(n = k + 1\). ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, the formula holds for every positive integer \(n\). ✓
05
Analysis
[5 marks]

Let \(y = \ln(1 + x)\), for \(x > -1\).

(a) Find \(\dfrac{dy}{dx}\), \(\dfrac{d^{2}y}{dx^{2}}\) and \(\dfrac{d^{3}y}{dx^{3}}\).

(b) Conjecture a formula for \(\dfrac{d^{n}y}{dx^{n}}\) and prove it by induction.

  • (a) \(\dfrac{dy}{dx} = (1 + x)^{-1}\), \(\dfrac{d^{2}y}{dx^{2}} = -(1 + x)^{-2}\), \(\dfrac{d^{3}y}{dx^{3}} = 2(1 + x)^{-3}\). ✓
  • (b) The sign alternates, the coefficients 1, 1, 2 are \(0!, 1!, 2!\), and the power is \(-n\). Conjecture \(\dfrac{d^{n}y}{dx^{n}} = \dfrac{(-1)^{n-1}(n - 1)!}{(1 + x)^{n}}\). ✓
  • Base case: \(n = 1\) gives \(\dfrac{(-1)^{0}\,0!}{1 + x} = \dfrac{1}{1 + x}\), which is \(\dfrac{dy}{dx}\). ✓
  • Assume \(\dfrac{d^{k}y}{dx^{k}} = (-1)^{k-1}(k - 1)!\,(1 + x)^{-k}\). Differentiate: \(\dfrac{d^{k+1}y}{dx^{k+1}} = (-1)^{k-1}(k - 1)! \times (-k)(1 + x)^{-k-1}\). ✓
  • \(= (-1)^{k}\,k!\,(1 + x)^{-(k+1)}\), since \((-1)^{k-1} \times (-1) = (-1)^{k}\) and \(k \times (k - 1)! = k!\). This is the formula with \(n = k + 1\). ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, the formula holds for every positive integer \(n\). ✓
06
Proof
[6 marks]

Let \(y = e^{x}\sin x\).

(a) Show that \(\dfrac{dy}{dx} = \sqrt{2}\,e^{x}\sin\!\big(x + \tfrac{\pi}{4}\big)\).

(b) Prove by induction that \(\dfrac{d^{n}y}{dx^{n}} = 2^{n/2}\,e^{x}\sin\!\big(x + \tfrac{n\pi}{4}\big)\) for every positive integer \(n\).

  • (a) \(\dfrac{dy}{dx} = e^{x}\sin x + e^{x}\cos x = e^{x}(\sin x + \cos x)\). ✓
  • \(\sin\!\big(x + \tfrac{\pi}{4}\big) = \sin x\cos\tfrac{\pi}{4} + \cos x\sin\tfrac{\pi}{4} = \tfrac{1}{\sqrt{2}}(\sin x + \cos x)\), so \(\sin x + \cos x = \sqrt{2}\sin\!\big(x + \tfrac{\pi}{4}\big)\) and \(\dfrac{dy}{dx} = \sqrt{2}\,e^{x}\sin\!\big(x + \tfrac{\pi}{4}\big)\). ✓
  • (b) Base case: \(n = 1\) gives \(2^{1/2}e^{x}\sin\!\big(x + \tfrac{\pi}{4}\big)\), which is part (a). ✓
  • Assume \(\dfrac{d^{k}y}{dx^{k}} = 2^{k/2}e^{x}\sin u\), where \(u = x + \tfrac{k\pi}{4}\). Product rule: \(\dfrac{d^{k+1}y}{dx^{k+1}} = 2^{k/2}e^{x}(\sin u + \cos u)\). ✓
  • By the identity in (a) with \(x\) replaced by \(u\): \(\sin u + \cos u = \sqrt{2}\sin\!\big(u + \tfrac{\pi}{4}\big)\), so \(\dfrac{d^{k+1}y}{dx^{k+1}} = 2^{(k+1)/2}e^{x}\sin\!\big(x + \tfrac{(k+1)\pi}{4}\big)\), the formula with \(n = k + 1\). ✓
  • True for \(n = 1\), and if true for \(n = k\) then true for \(n = k + 1\). Hence, by mathematical induction, the formula holds for every positive integer \(n\). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.