Proof by Mathematical Induction

Mathematical induction is the technique for proving that a statement $P(n)$P(n) holds for every integer from some starting point onwards. The idea is a chain of dominoes: knock over the first (the base case), and show that each domino knocks over the next (the inductive step), and the whole infinite row must fall. It is the signature proof method of Further Mathematics, examined explicitly and also woven through complex numbers (De Moivre), matrices (powers), and series.

This lesson sets out the rigorous four-part structure, then drills it across the four question types you will meet — summation formulae, divisibility, matrix powers and recurrence relations — with the precise wording examiners look for.

---

Where this sits in AQA 7367

This is the proof by induction strand of the compulsory pure content examined on Paper 1 and Paper 2 (each 2 hours, 100 marks, 33⅓% of the A-Level). It is the workhorse of AO2 (constructing a rigorous argument and communicating it), and it underpins later results you prove by induction — De Moivre's theorem, the formula for $A^n$An, and the standard summation results. Marks here are won less on the algebra than on stating every part of the structure: a flawless inductive step with no conclusion still loses marks.

---

Core theory: the four-part structure

To prove $P(n)$P(n) is true for all integers $n \ge n_0$n≥n0​ (usually $n_0 = 1$n0​=1):

1. Base case. Verify $P(n_0)$P(n0​) directly — show LHS $=$= RHS (or the divisibility/matrix claim) at the starting value.
2. Inductive hypothesis. Assume $P(k)$P(k) is true for some integer $k \ge n_0$k≥n0​. State this explicitly — it is the assumption you are allowed to use.
3. Inductive step. Using the hypothesis, prove $P(k+1)$P(k+1) follows. This is the heart of the proof: the assumed $P(k)$P(k) must visibly appear.
4. Conclusion. State: "Since $P(n_0)$P(n0​) is true, and $P(k)$P(k) true $\Rightarrow P(k+1)$⇒P(k+1) true, by the principle of mathematical induction $P(n)$P(n) is true for all $n \ge n_0$n≥n0​."

Why this is valid, not circular. Assuming $P(k)$P(k) is not assuming what you want to prove. You prove the implication $P(k)\Rightarrow P(k+1)$P(k)⇒P(k+1) — a conditional. Combined with the base case $P(1)$P(1), the implication fires repeatedly: $P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow\cdots$P(1)⇒P(2)⇒P(3)⇒⋯, reaching every $n$n. Omitting either the base case or the implication breaks the chain.

A reliable habit in the inductive step is to start from the $P(k+1)$P(k+1) expression, split off the new piece, and substitute the hypothesis — never start by writing the answer you are heading for, which looks circular.

The logic, made precise

It pays to be clear about what each part contributes, because the marks track the logic exactly. The base case establishes a single true instance, $P(n_0)$P(n0​). The inductive step establishes the conditional "for every $k \ge n_0$k≥n0​, if $P(k)$P(k) then $P(k+1)$P(k+1)" — note it proves an implication, and proving an implication is allowed to assume its antecedent $P(k)$P(k). Modus ponens then chains the two: from $P(n_0)$P(n0​) and $P(n_0)\Rightarrow P(n_0+1)$P(n0​)⇒P(n0​+1) we get $P(n_0+1)$P(n0​+1); from that and the next instance of the implication we get $P(n_0+2)$P(n0​+2); and so on without end. The conclusion simply names this principle and records the range of $n$n reached.

This is why both halves are indispensable and neither alone suffices. A statement can satisfy the inductive step yet be false everywhere because the base case fails — for example, "$n = n + 1$n=n+1" trivially satisfies $P(k)\Rightarrow P(k+1)$P(k)⇒P(k+1) (add 1 to both sides) but has no true base case, so it is never true. Conversely a true base case with no working implication proves only that one instance holds. The examiner's mark scheme mirrors this: a mark for the base case, marks for a correctly used hypothesis in the step, and a mark for the conclusion — lose any one and the proof is logically incomplete.

---

Worked examples (with mark scheme)

Example 1 — a summation formula

Prove that $\displaystyle\sum_{r=1}^{n} r = \frac{n(n+1)}{2}$r=1∑n​r=2n(n+1)​ for all $n \ge 1$n≥1.

Base case $(n=1)$(n=1): LHS $= 1$=1; RHS $= \dfrac{1\cdot 2}{2} = 1$=21⋅2​=1. LHS $=$= RHS, so $P(1)$P(1) holds. $(\text{B1})$(B1)

Hypothesis: assume $\displaystyle\sum_{r=1}^{k} r = \dfrac{k(k+1)}{2}$r=1∑k​r=2k(k+1)​ for some $k \ge 1$k≥1. $(\text{M1 state hypothesis})$(M1 state hypothesis)

Inductive step: split off the $(k+1)$(k+1)th term and substitute the hypothesis:

$\sum_{r=1}^{k+1} r = \sum_{r=1}^{k} r + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}. \quad (\text{M1 use HoP; A1})$∑r=1k+1​r=∑r=1k​r+(k+1)=2k(k+1)​+(k+1)=2k(k+1)+2(k+1)​=2(k+1)(k+2)​.(M1 use HoP; A1)

This is the formula with $n = k+1$n=k+1. $(\text{A1})$(A1)

Conclusion: since $P(1)$P(1) is true and $P(k)\Rightarrow P(k+1)$P(k)⇒P(k+1), by mathematical induction the result holds for all $n \ge 1$n≥1. $(\text{A1 conclusion})$(A1 conclusion)

(B1 base case; M1 stating the hypothesis; M1 splitting off the new term and using it; A1 reaching $\tfrac{(k+1)(k+2)}{2}$2(k+1)(k+2)​; A1 for an explicit conclusion. The final A-mark is for the conclusion — routinely dropped by candidates who stop at the algebra.)

The engine of a summation induction is the single line $\sum_{r=1}^{k+1} = \sum_{r=1}^{k} + (k+1)\text{th term}$∑r=1k+1​=∑r=1k​+(k+1)th term: you peel off the last term, replace the remaining sum by the hypothesis, and tidy. The "tidy" step is pure algebra, and it is where the A-mark for reaching the $k+1$k+1 form lives — so make the common factor explicit ($(k+1)$(k+1) here) rather than expanding and re-factorising. A useful final flourish, shown in the top-band answer below, is to write out what $P(k+1)$P(k+1) should look like (substitute $k+1$k+1 for $n$n in the original formula) and observe that your simplified expression matches it. That removes any ambiguity about whether you have actually reached the target — a small habit that converts a "probably correct" step into a watertight one.

Example 2 — divisibility

Prove that $6^n - 1$6n−1 is divisible by 5 for all $n \ge 1$n≥1.

Base case $(n=1)$(n=1): $6^1 - 1 = 5 = 5\times 1$61−1=5=5×1, divisible by 5. $(\text{B1})$(B1)

Hypothesis: assume $6^k - 1 = 5m$6k−1=5m for some integer $m$m, i.e. $6^k = 5m + 1$6k=5m+1. $(\text{M1})$(M1)

Inductive step:

$6^{k+1} - 1 = 6\cdot 6^k - 1 = 6(5m + 1) - 1 = 30m + 5 = 5(6m + 1). \quad (\text{M1 substitute; A1 factor of 5})$6k+1−1=6⋅6k−1=6(5m+1)−1=30m+5=5(6m+1).(M1 substitute; A1 factor of 5)

Since $6m + 1$6m+1 is an integer, $6^{k+1} - 1$6k+1−1 is divisible by 5. $(\text{A1})$(A1)

Conclusion: by mathematical induction, $6^n - 1$6n−1 is divisible by 5 for all $n \ge 1$n≥1. $(\text{A1})$(A1)

(The decisive move is rewriting the hypothesis as $6^k = 5m+1$6k=5m+1 and substituting it, so that a factor of 5 falls out cleanly. M1 substitute; A1 explicit factor of 5; A1 conclusion.)

There is a standard technique here worth naming, because every divisibility induction uses a version of it. You want to relate $P(k+1)$P(k+1) to $P(k)$P(k), so you manufacture the assumed expression: write $6^{k+1} - 1 = 6\cdot 6^k - 1$6k+1−1=6⋅6k−1 and then add and subtract to expose $6^k - 1$6k−1, or — as above — substitute $6^k = 5m + 1$6k=5m+1 directly. An equivalent route some candidates prefer is $6^{k+1} - 1 = 6(6^k - 1) + 5 = 6\cdot 5m + 5 = 5(6m + 1)$6k+1−1=6(6k−1)+5=6⋅5m+5=5(6m+1), which uses the hypothesis in the form $6^k - 1 = 5m$6k−1=5m without rearranging. Both are fully valid; the marker only requires that the hypothesis is visibly used and that a factor of the divisor is extracted. Pick whichever form you find less error-prone and apply it consistently.

Example 3 — a matrix power

Let $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$A=(10​11​). Prove that $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$An=(10​n1​) for all $n \ge 1$n≥1.

Base case $(n=1)$(n=1): $A^1 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$A1=(10​11​)=(10​11​) ✓. $(\text{B1})$(B1)

Hypothesis: assume $A^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$Ak=(10​k1​). $(\text{M1})$(M1)

Inductive step: $A^{k+1} = A^k A$Ak+1=AkA, using the hypothesis for $A^k$Ak:

$A^{k+1} = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1\cdot1 + k\cdot0 & 1\cdot1 + k\cdot1 \\ 0\cdot1 + 1\cdot0 & 0\cdot1 + 1\cdot1 \end{pmatrix} = \begin{pmatrix} 1 & k+1 \\ 0 & 1 \end{pmatrix}. \quad (\text{M1 multiply; A1})$Ak+1=(10​k1​)(10​11​)=(1⋅1+k⋅00⋅1+1⋅0​1⋅1+k⋅10⋅1+1⋅1​)=(10​k+11​).(M1 multiply; A1)

This is the result with $n = k+1$n=k+1. $(\text{A1})$(A1)

Conclusion: by mathematical induction, $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$An=(10​n1​) for all $n \ge 1$n≥1. $(\text{A1})$(A1)

(Write $A^{k+1} = A^k A$Ak+1=AkA — using the hypothesis on $A^k$Ak — not $A\,A^k$AAk with the hypothesis on the wrong factor; show the matrix multiplication explicitly for the M1.)

Example 4 — a recurrence relation

A sequence is defined by $u_1 = 1$u1​=1 and $u_{n+1} = 3u_n + 2$un+1​=3un​+2. Prove that $u_n = 2\cdot 3^{n-1} - 1$un​=2⋅3n−1−1 for all $n \ge 1$n≥1.

Base case $(n=1)$(n=1): $u_1 = 2\cdot 3^{0} - 1 = 2 - 1 = 1$u1​=2⋅30−1=2−1=1 ✓. $(\text{B1})$(B1)

Hypothesis: assume $u_k = 2\cdot 3^{k-1} - 1$uk​=2⋅3k−1−1. $(\text{M1})$(M1)

Inductive step: use the recurrence, then the hypothesis:

$u_{k+1} = 3u_k + 2 = 3\big(2\cdot 3^{k-1} - 1\big) + 2 = 2\cdot 3^{k} - 3 + 2 = 2\cdot 3^{k} - 1. \quad (\text{M1 use recurrence and HoP; A1})$uk+1​=3uk​+2=3(2⋅3k−1−1)+2=2⋅3k−3+2=2⋅3k−1.(M1 use recurrence and HoP; A1)

This is the formula with $n = k+1$n=k+1 (since $3^{(k+1)-1} = 3^{k}$3(k+1)−1=3k). $(\text{A1})$(A1)

Conclusion: by mathematical induction, $u_n = 2\cdot 3^{n-1} - 1$un​=2⋅3n−1−1 for all $n \ge 1$n≥1. $(\text{A1})$(A1)

(The two-stage substitution — first the recurrence $u_{k+1} = 3u_k + 2$uk+1​=3uk​+2, then the hypothesis for $u_k$uk​ — is the crux; missing either loses an M-mark.)

Recurrence inductions have a structure all four worked examples share but which is most visible here: there are two given facts, and you must use both. The recurrence $u_{k+1} = 3u_k + 2$uk+1​=3uk​+2 tells you how to get from the $k$kth term to the $(k+1)$(k+1)th; the inductive hypothesis tells you a closed form for the $k$kth term. Apply them in that order — recurrence first to introduce $u_k$uk​, then hypothesis to replace it — and the algebra resolves to the closed form at $k+1$k+1. A subtlety that catches people out is the index arithmetic in the exponent: the target $P(k+1)$P(k+1) is $u_{k+1} = 2\cdot 3^{(k+1)-1} - 1 = 2\cdot 3^{k} - 1$uk+1​=2⋅3(k+1)−1−1=2⋅3k−1, so you are aiming for $3^k$3k, not $3^{k+1}$3k+1. Always write down the target form explicitly before declaring victory; misreading the exponent is the commonest slip in recurrence inductions.

(specimen-style — not from any past paper)

Prove by induction that $\,9^n - 1\,$9n−1 is divisible by 8 for all positive integers $n$n.

Base case $(n=1)$(n=1): $9^1 - 1 = 8$91−1=8, divisible by 8 ✓.

Hypothesis: assume $9^k - 1 = 8m$9k−1=8m for some integer $m$m, i.e. $9^k = 8m + 1$9k=8m+1.

Inductive step:

$9^{k+1} - 1 = 9\cdot 9^k - 1 = 9(8m + 1) - 1 = 72m + 8 = 8(9m + 1),$9k+1−1=9⋅9k−1=9(8m+1)−1=72m+8=8(9m+1),

which is divisible by 8 (as $9m + 1\in\mathbb{Z}$9m+1∈Z).

Conclusion: since the result holds for $n=1$n=1 and $P(k)\Rightarrow P(k+1)$P(k)⇒P(k+1), by mathematical induction $9^n - 1$9n−1 is divisible by 8 for all positive integers $n$n.

The command word "Prove by induction" makes the structure part of what is assessed: even a candidate who spots that $9^n - 1 = (9-1)(9^{n-1} + \cdots + 1)$9n−1=(9−1)(9n−1+⋯+1) directly must still give the four-part induction to earn the marks — the question dictates the method. This is a general feature of command words in mathematics: "prove by induction", "using the substitution …", "by considering …" all prescribe the method, and a correct answer by a different route scores little. Read the command word as a constraint, not a suggestion.