Home / A-Level Further Maths 9231 / Proof by induction / Proof by induction: divisibility, matrices and derivatives
Cambridge International AS & A Level · Topic 1.7
A-Level Further Maths 9231 / Topic 1.7 / AS & A Level

One more power, one more product, one more derivative.

The four-part induction proof from sums works for much more. To prove that an expression is always a multiple of 8, that a matrix power has a formula in \(n\), or that the \(n\)th derivative of \(xe^{2x}\) follows a pattern, you keep the same base case, assumption and conclusion, and change only the inductive step.

Topic 1.7All proof by induction lessons →
The key idea

Every induction proof has the same frame: show \(P(1)\) is true; assume \(P(k)\) is true for some positive integer \(k\); use that assumption to show \(P(k + 1)\) is true; then write the conclusion. Only the step changes. Divisibility: assume \(f(k) = dm\) and write \(f(k + 1) - c\,f(k)\), where \(c\) is the base of a power in \(f\), so that what is left is visibly a multiple of \(d\). Matrix powers: \(\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M}\), with the assumed matrix put in for \(\mathbf{M}^{k}\). Derivatives: the \((k + 1)\)th derivative is the derivative of the assumed \(k\)th derivative. When no formula is given, work out the first few cases, conjecture the pattern, then prove it.

… … n = 1 2 3 k k + 1 base case: P(1) is true step: P(k) ⇒ P(k + 1) divisibility: f(k + 1) − c·f(k) = a multiple of d matrices: Mk + 1 = MkM, with the assumed Mk derivatives: differentiate the assumed k th derivative
Fig. 1: induction as a row of dominoes. The base case knocks over the first; the inductive step shows that whenever domino k falls, domino k + 1 falls too, so every domino falls. Only the step changes from one kind of proof to another
Section 01

Divisibility: make the remainder visible.

To prove that \(f(n)\) is divisible by \(d\) for every positive integer \(n\), let \(P(n)\) be the statement '\(f(n)\) is divisible by \(d\)'. The assumption is \(f(k) = dm\) for some integer \(m\). The task in the step is to show that \(f(k + 1)\) is also \(d\) times an integer. The tool is the index law \(a^{k+1} = a \cdot a^{k}\): it lets you compare \(f(k + 1)\) with a multiple of \(f(k)\).

Worked example Substitute the assumption
Prove by induction that \(6^{n} + 4\) is divisible by 5 for every positive integer \(n\).
  1. Let \(P(n)\) be the statement '\(6^{n} + 4\) is divisible by 5'. Base case: when \(n = 1\), \(6 + 4 = 10 = 5 \times 2\), so \(P(1)\) is true.
  2. Assume \(P(k)\) is true for some positive integer \(k\): \(6^{k} + 4 = 5m\) for some integer \(m\), so \(6^{k} = 5m - 4\).
  3. Then \(6^{k+1} + 4 = 6 \cdot 6^{k} + 4 = 6(5m - 4) + 4 = 30m - 20 = 5(6m - 4)\).
  4. \(6m - 4\) is an integer, so \(6^{k+1} + 4\) is divisible by 5 and \(P(k + 1)\) is true.
  5. \(P(1)\) is true, and if \(P(k)\) is true then \(P(k + 1)\) is true. Hence, by mathematical induction, \(6^{n} + 4\) is divisible by 5 for every positive integer \(n\).
Answer: Proved: \(6^{k+1} + 4 = 5(6m - 4)\) carries the divisibility from \(k\) to \(k + 1\)
Worked example Two different powers
Prove by induction that \(f(n) = 2^{n+2} + 3^{2n+1}\) is divisible by 7 for every positive integer \(n\).
  1. Base case: \(f(1) = 2^{3} + 3^{3} = 8 + 27 = 35 = 7 \times 5\), so the result holds for \(n = 1\).
  2. Assume it holds for \(n = k\): \(f(k) = 2^{k+2} + 3^{2k+1} = 7m\) for some integer \(m\).
  3. \(f(k + 1) = 2^{k+3} + 3^{2k+3} = 2 \cdot 2^{k+2} + 9 \cdot 3^{2k+1}\).
  4. Split \(9 = 2 + 7\): \(f(k + 1) = 2\big(2^{k+2} + 3^{2k+1}\big) + 7 \cdot 3^{2k+1} = 2f(k) + 7 \cdot 3^{2k+1}\).
  5. So \(f(k + 1) = 14m + 7 \cdot 3^{2k+1} = 7\big(2m + 3^{2k+1}\big)\), a multiple of 7.
  6. The result is true for \(n = 1\), and if it is true for \(n = k\) it is true for \(n = k + 1\). Hence, by mathematical induction, \(f(n)\) is divisible by 7 for every positive integer \(n\).
Answer: Proved, using \(f(k + 1) - 2f(k) = 7 \cdot 3^{2k+1}\)
Your turn
Prove by induction that \(11^{n} - 4^{n}\) is divisible by 7 for every positive integer \(n\).
Examiner trap

\(6^{k+1} + 4\) is NOT \(6(6^{k} + 4)\): the 6 multiplies the power only, and \(6(6^{k} + 4) = 6^{k+1} + 24\). Keep the constant outside: \(6^{k+1} + 4 = 6 \cdot 6^{k} + 4\). Also assume \(P(k)\) 'for some positive integer \(k\)', never 'for all \(k\)': that is what you are trying to prove.

Section 02

Matrix powers: multiply once more.

To prove that \(\mathbf{M}^{n}\) equals a given matrix whose entries depend on \(n\), the inductive step is a single matrix multiplication. Write down the target \(\mathbf{M}^{k+1}\) first (the formula with \(n\) replaced by \(k + 1\)), then work towards it using the one identity below.

\[\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M}.\]
Worked example Prove a given formula
The matrix \(\mathbf{M} = \begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix}\). Prove by induction that \(\mathbf{M}^{n} = \begin{pmatrix} 3^{n} & 3^{n} - 1 \\ 0 & 1 \end{pmatrix}\) for every positive integer \(n\).
  1. Base case: \(n = 1\) gives \(\begin{pmatrix} 3 & 3 - 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix} = \mathbf{M}\), so the formula holds for \(n = 1\).
  2. Assume \(\mathbf{M}^{k} = \begin{pmatrix} 3^{k} & 3^{k} - 1 \\ 0 & 1 \end{pmatrix}\) for some positive integer \(k\). Target: \(\mathbf{M}^{k+1} = \begin{pmatrix} 3^{k+1} & 3^{k+1} - 1 \\ 0 & 1 \end{pmatrix}\).
  3. \(\mathbf{M}^{k+1} = \mathbf{M}^{k}\mathbf{M} = \begin{pmatrix} 3^{k} & 3^{k} - 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix}\)
  4. \(= \begin{pmatrix} 3 \cdot 3^{k} & 2 \cdot 3^{k} + 3^{k} - 1 \\ 0 & 1 \end{pmatrix}\), which is \(\begin{pmatrix} 3^{k+1} & 3^{k+1} - 1 \\ 0 & 1 \end{pmatrix}\), since \(2 \cdot 3^{k} + 3^{k} = 3 \cdot 3^{k}\).
  5. The formula is true for \(n = 1\), and if it is true for \(n = k\) it is true for \(n = k + 1\). Hence, by mathematical induction, it is true for every positive integer \(n\).
Answer: Proved: \(\mathbf{M}^{k}\mathbf{M}\) gives the formula with \(n = k + 1\)
Worked example Conjecture, then prove
The matrix \(\mathbf{A} = \begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}\). Find \(\mathbf{A}^{2}\) and \(\mathbf{A}^{3}\), conjecture a formula for \(\mathbf{A}^{n}\) and prove it by induction.
  1. \(\mathbf{A}^{2} = \begin{pmatrix} 3 & -2 \\ 2 & -1 \end{pmatrix}\) and \(\mathbf{A}^{3} = \mathbf{A}^{2}\mathbf{A} = \begin{pmatrix} 4 & -3 \\ 3 & -2 \end{pmatrix}\).
  2. Entry by entry for \(n = 1, 2, 3\): top left 2, 3, 4; top right \(-1, -2, -3\); bottom left 1, 2, 3; bottom right \(0, -1, -2\). Each goes up or down by 1. Conjecture \(\mathbf{A}^{n} = \begin{pmatrix} n + 1 & -n \\ n & 1 - n \end{pmatrix}\).
  3. Base case: \(n = 1\) gives \(\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix} = \mathbf{A}\).
  4. Assume \(\mathbf{A}^{k} = \begin{pmatrix} k + 1 & -k \\ k & 1 - k \end{pmatrix}\). Then \(\mathbf{A}^{k+1} = \mathbf{A}^{k}\mathbf{A}\), which is \(\begin{pmatrix} 2(k + 1) - k & -(k + 1) \\ 2k + (1 - k) & -k \end{pmatrix}\)
  5. \(= \begin{pmatrix} (k + 1) + 1 & -(k + 1) \\ k + 1 & 1 - (k + 1) \end{pmatrix}\), which is the conjecture with \(n = k + 1\).
  6. True for \(n = 1\), and true for \(n = k + 1\) whenever true for \(n = k\), so by mathematical induction it is true for every positive integer \(n\).
Answer: \(\mathbf{A}^{n} = \begin{pmatrix} n + 1 & -n \\ n & 1 - n \end{pmatrix}\)
Your turn
Prove by induction that \(\begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}^{n} = \begin{pmatrix} 1 & 0 \\ 3n & 1 \end{pmatrix}\) for every positive integer \(n\).
Examiner trap

A pattern in \(\mathbf{M}^{2}\), \(\mathbf{M}^{3}\) and \(\mathbf{M}^{4}\) is only a conjecture; the marks are for the induction that follows. In the step, multiply rows by columns: multiplying \(\mathbf{M}^{k}\) and \(\mathbf{M}\) entry by entry is not matrix multiplication and gives the wrong matrix.

Stage 1 · Learn

Check your understanding

Four quick checks. Each correct answer earns XP and records this skill on your profile.

Quick check+10 XP

For \(f(n) = 4^{n} + 2\), which expression equals \(f(k + 1) - 4f(k)\)?

Quick check+10 XP

In proving a formula for \(\mathbf{M}^{n}\) by induction, the inductive step works out

Quick check+10 XP

Assume \(6^{k} + 4 = 5m\) for an integer \(m\). Which expression equals \(6^{k+1} + 4\)?

Quick check+10 XP

\(\mathbf{M} = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}\). Which formula for \(\mathbf{M}^{n}\) fits \(\mathbf{M}^{2}\) and \(\mathbf{M}^{3}\)?

Section 03

nth derivatives: differentiate the assumption.

\(\dfrac{d^{n}y}{dx^{n}}\) means \(y\) differentiated \(n\) times. The \((k + 1)\)th derivative is the derivative of the \(k\)th, so the inductive step is: take the ASSUMED expression for \(\dfrac{d^{k}y}{dx^{k}}\), differentiate it once (usually with the product rule) and tidy it into the formula with \(n = k + 1\).

\[\frac{d^{k+1}y}{dx^{k+1}} = \frac{d}{dx}\left(\frac{d^{k}y}{dx^{k}}\right)\]
Worked example Prove a given formula
Given \(y = xe^{2x}\), prove by induction that \(\dfrac{d^{n}y}{dx^{n}} = 2^{n-1}(2x + n)e^{2x}\) for every positive integer \(n\).
  1. Base case: \(\dfrac{dy}{dx} = e^{2x} + 2xe^{2x} = (2x + 1)e^{2x}\), and the formula at \(n = 1\) gives \(2^{0}(2x + 1)e^{2x}\). They agree.
  2. Assume \(\dfrac{d^{k}y}{dx^{k}} = 2^{k-1}(2x + k)e^{2x}\) for some positive integer \(k\). Target: \(2^{k}\big(2x + (k + 1)\big)e^{2x}\).
  3. Product rule: \(\dfrac{d^{k+1}y}{dx^{k+1}} = 2^{k-1}\big[2e^{2x} + (2x + k) \cdot 2e^{2x}\big]\).
  4. \(= 2^{k-1} \cdot 2\,(1 + 2x + k)e^{2x} = 2^{k}\big(2x + (k + 1)\big)e^{2x}\), the formula with \(n = k + 1\).
  5. True for \(n = 1\), and true for \(n = k + 1\) whenever true for \(n = k\). Hence, by mathematical induction, true for every positive integer \(n\).
Answer: Proved: \(\dfrac{d^{n}y}{dx^{n}} = 2^{n-1}(2x + n)e^{2x}\)
Worked example Conjecture, then prove
Given \(y = x^{2}e^{x}\), find the first three derivatives, conjecture a formula for \(\dfrac{d^{n}y}{dx^{n}}\) and prove it by induction.
  1. \(y' = (x^{2} + 2x)e^{x}\), \(y'' = (x^{2} + 4x + 2)e^{x}\), \(y''' = (x^{2} + 6x + 6)e^{x}\).
  2. The \(x\) coefficient is 2, 4, 6, that is \(2n\). The constant is 0, 2, 6, that is \(n(n - 1)\). Conjecture \(\dfrac{d^{n}y}{dx^{n}} = \big(x^{2} + 2nx + n(n - 1)\big)e^{x}\).
  3. Base case: \(n = 1\) gives \((x^{2} + 2x + 0)e^{x} = y'\).
  4. Assume \(\dfrac{d^{k}y}{dx^{k}} = \big(x^{2} + 2kx + k(k - 1)\big)e^{x}\). Differentiate: \((2x + 2k)e^{x} + \big(x^{2} + 2kx + k(k - 1)\big)e^{x}\)
  5. \(= \big(x^{2} + 2(k + 1)x + k^{2} + k\big)e^{x}\), and \(k^{2} + k = (k + 1)k\), so this is the conjecture with \(n = k + 1\).
  6. True for \(n = 1\), and true for \(n = k + 1\) whenever true for \(n = k\), so by mathematical induction it is true for every positive integer \(n\).
Answer: \(\dfrac{d^{n}y}{dx^{n}} = \big(x^{2} + 2nx + n(n - 1)\big)e^{x}\)
Your turn
Given \(y = xe^{-x}\), prove by induction that \(\dfrac{d^{n}y}{dx^{n}} = (-1)^{n}(x - n)e^{-x}\) for every positive integer \(n\).
Examiner trap

In the step, differentiate the ASSUMED \(k\)th derivative, not \(y\) again, and keep the chain rule factor: \(\dfrac{d}{dx}e^{2x} = 2e^{2x}\), not \(e^{2x}\). The base case is the first derivative (\(n = 1\)), not \(y\) itself, unless the question includes \(n = 0\).

Stage 2 · Exam

Exam-style questions

Unlocks once the four checks above are done. Worth more XP, written to AS & A Level Further Mathematics Paper 1 to 4 standard.

Finish the four checks above to unlock the exam questions
Exam style+20 XP

Let \(f(n) = 3^{2n} + 7\). Which expression for \(f(k + 1)\) shows that \(f(n)\) is divisible by 8 for every positive integer \(n\)?

Exam style+20 XP

\(\mathbf{M} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}\) and you assume \(\mathbf{M}^{k} = \begin{pmatrix} 2^{k} & 2^{k} - 1 \\ 0 & 1 \end{pmatrix}\). What is the top right entry of \(\mathbf{M}^{k}\mathbf{M}\)?

Exam style+20 XP

Given \(y = xe^{-2x}\), which formula for \(\dfrac{d^{n}y}{dx^{n}}\) is correct for every positive integer \(n\)?

Exam style+20 XP

Let \(f(n) = 4^{n} + 15n - 1\), and assume \(f(k)\) is divisible by 9. Which expression is \(f(k + 1) - 4f(k)\)?

Skill unlocked

Further Pure 1 complete: proofs carried from k to k + 1.

This skill is now recorded on your profile. Keep the chain going.

-Rank -Level -Score -Topics
Go deeper · practice
Six original Cambridge-style questions
Two divisibility proofs with one power, one with two powers and a constant, a matrix power to conjecture and prove, the \(n\)th derivative of \(\ln(1 + x)\), and \(e^{x}\sin x\) with a compound angle.