Proof
FP1 Topic 8, spec point by spec point (Proof). Each spec point has the method, worked examples written the way the mark scheme wants them, how the marks go and the mistakes that cost the most marks.
Spec8.1Proof by mathematical induction
Prove results by induction for sums of series, divisibility, general terms of recurrence relations and matrix powers.
The idea: dominoes
To show a statement is true for every positive integer \(n\):
- Basis: show it's true for \(n = 1\) (the first domino falls).
- Assumption: assume it's true for \(n = k\).
- Inductive step: use that to show it's true for \(n = k + 1\) (each domino knocks over the next).
- Conclusion: so it's true for all positive integers \(n\).
The conclusion is worth a mark. Use wording like: "If the result is true for \(n = k\), then it is true for \(n = k + 1\). As it is true for \(n = 1\), it is true for all positive integers \(n\)."
The four types and their inductive step
| Type | Inductive step |
|---|---|
| Sum of a series | \(\sum_{r=1}^{k+1} = \left(\sum_{r=1}^{k}\right) + (k + 1)\text{th term}\). Factorise towards the formula with \(n = k + 1\). |
| Divisibility | Find \(f(k + 1) - f(k)\) (or \(f(k + 1) - mf(k)\)) and show it is a multiple of the divisor. Then \(f(k + 1) = f(k) + \text{multiple}\). |
| Recurrence relation | \(u_{k+1} = (\text{rule applied to } u_k)\), using the assumed formula for \(u_k\). |
| Matrix powers | \(\mathbf{M}^{k+1} = \mathbf{M}^k\mathbf{M}\), multiply, and simplify each entry to the form with \(n = k + 1\). |
Know your target: write down what the formula looks like with \(n = k + 1\) before you start the algebra.
a sum
Prove \(\displaystyle\sum_{r=1}^{n} r(r + 1) = \frac{n(n + 1)(n + 2)}{3}\).
\(n = 1\): LHS \(= 2\), RHS \(= \frac{1 \cdot 2 \cdot 3}{3} = 2\). True.
Assume true for \(n = k\). Then \(\sum_{r=1}^{k+1} r(r + 1) = \frac{k(k + 1)(k + 2)}{3} + (k + 1)(k + 2) = \frac{(k + 1)(k + 2)(k + 3)}{3}\).
This is the formula with \(n = k + 1\). Conclusion as above.
divisibility
Prove \(f(n) = 3^{2n} + 11\) is divisible by 4 for all positive integers \(n\).
\(f(1) = 9 + 11 = 20 = 4 \times 5\). True.
Assume \(f(k)\) is divisible by 4. \(f(k + 1) - f(k) = 3^{2k + 2} - 3^{2k} = 9 \cdot 3^{2k} - 3^{2k} = 8 \cdot 3^{2k}\).
So \(f(k + 1) = f(k) + 8 \cdot 3^{2k}\): both terms are divisible by 4, so \(f(k + 1)\) is. Conclusion.
a recurrence
\(u_1 = 1\) and \(u_{n+1} = 3u_n + 4\). Prove \(u_n = 3^n - 2\).
\(n = 1\): \(3 - 2 = 1\). True.
Assume \(u_k = 3^k - 2\). Then \(u_{k+1} = 3(3^k - 2) + 4 = 3^{k+1} - 2\). Conclusion.
a matrix power
Prove \(\begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}^n = \begin{pmatrix} 1 - 3n & -n \\ 9n & 3n + 1 \end{pmatrix}\).
\(n = 1\): \(\begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}\) ✓.
Assume true for \(n = k\). \(\begin{pmatrix} 1 - 3k & -k \\ 9k & 3k + 1 \end{pmatrix}\begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix} = \begin{pmatrix} -2 - 3k & -1 - k \\ 9k + 9 & 3k + 4 \end{pmatrix}\)
\(= \begin{pmatrix} 1 - 3(k + 1) & -(k + 1) \\ 9(k + 1) & 3(k + 1) + 1 \end{pmatrix}\). Conclusion.
- B1 for the basis with both sides evaluated, M1 for adding the \((k + 1)\)th term to the assumed sum, A1 for taking out a common factor, A1 for reaching the \(n = k + 1\) form, A1 cso for a full conclusion (WFM01A Jan 2026 Q10).
- Divisibility: B1 for \(f(1)\), M1 for \(f(k + 1) - f(k)\) (or a multiple), A1 A1 for a valid split, dM1 for making \(f(k + 1)\) the subject, A1 cso (WFM01 Jun 2019 Q8).
- Unusual sums, e.g. with logs, need the same structure (WFM01 Jan 2023 Q9).
Often asked as: one induction question on every FP1 paper; any of the four types.
Basis "\(1 = 1\)" without showing both sides.
Expanding everything instead of factorising out \((k + 1)\).
A weak or missing conclusion.