HookFermat checked five cases — the sixth blew up
In 1640 Pierre de Fermat wrote to his correspondents with a discovery: every number of the form \(2^{2^n}+1\) is prime. Check them and the claim looks unstoppable — \(3\), \(5\), \(17\), \(257\), \(65{,}537\): five values, five primes. Fermat admitted he had no proof, but told Frénicle de Bessy he was all but certain. Ninety-two years later Leonhard Euler sat down with the sixth case and factorised it: \(2^{32}+1=4{,}294{,}967{,}297=641\times 6{,}700{,}417\). Not prime. Five confirmations, and the pattern was dead on the very next number.
That is the problem this section exists to solve. A claim about every positive integer covers infinitely many cases, and no amount of checking — five, five thousand, five billion — settles it. Mathematical induction is the finite argument that closes an infinite family of cases for good, and AQA's spec statement A1 asks you to run it in three arenas: summation formulae for series, divisibility results, and powers of a matrix. The machinery is identical every time; only the algebra in the middle changes. Learn the engine once, then learn the three fuel types.
ModelOne engine, four moves
Every induction proof is the same four moves, and AQA's mark scheme tracks them one by one. Call the claim \(P(n)\) — 'the formula holds for \(n\)'. Move 1, the basis case: verify \(P(1)\) directly, evaluating both sides separately and showing they agree. Move 2, the inductive hypothesis: assume the result holds for \(n=k\), where \(k\) is one unspecified positive integer — not for all \(n\), which would be assuming the theorem itself. Move 3, the inductive step: using that assumption, prove the result for \(n=k+1\). The hypothesis must visibly appear in the working; a 'step' that never uses it is not induction. Move 4, the conclusion: one sentence tying it together — the result holds for \(n=1\), and holding at \(n=k\) forces it at \(n=k+1\), so it holds for all positive integers \(n\) by induction.
Why is that a proof? Because the two facts reach every case in finitely many steps: truth at \(1\) gives truth at \(2\), which gives truth at \(3\), and any given integer is only ever a finite chain of implications away from the basis. Fermat had five isolated checks; induction welds each case to the next so that nothing after the anchor can ever break.
MechanismSummation formulae: aim before you fire
For a series proof the target is everything. Before touching the algebra, write out what \(P(k+1)\) actually says — the claimed formula with every \(n\) replaced by \(k+1\) — because the whole inductive step is a controlled journey to that exact expression. The step itself always opens the same way: the sum to \(k+1\) terms is the sum to \(k\) terms plus the \((k+1)\)th term, and the sum to \(k\) terms is what the hypothesis lets you replace with the closed form.
From there, resist the urge to multiply everything out. The target is factorised, so stay factorised: pull out the common factor — almost always \((k+1)\) — early, and steer the remaining bracket towards what the target needs. Expanding into a cubic and refactorising wastes time and invites sign errors, and the accuracy mark sits on the final, visibly correct form. The standard results for \(\sum r\), \(\sum r^2\) and \(\sum r^3\) that you will lean on throughout the series section are themselves provable exactly this way — induction is where the certainty of those formulae comes from.
Prove that \(\sum_{r=1}^{n} r(3r+1)=n(n+1)^2\) for all positive integers \(n\).
Basis: for \(n=1\), the left side is \(1\times 4=4\) and the right side is \(1\times 2^2=4\). Equal, so the result holds at \(n=1\).
Hypothesis: assume \(\sum_{r=1}^{k} r(3r+1)=k(k+1)^2\) for some positive integer \(k\). Step: the target is \((k+1)(k+2)^2\). Now \[\sum_{r=1}^{k+1} r(3r+1)=k(k+1)^2+(k+1)\big(3(k+1)+1\big)=(k+1)\big[k(k+1)+3k+4\big].\] The bracket is \(k^2+4k+4=(k+2)^2\), so the sum is \((k+1)(k+2)^2=(k+1)\big((k+1)+1\big)^2\) — the formula with \(n=k+1\).
Conclusion: the result is true for \(n=1\), and true for \(n=k\) implies true for \(n=k+1\); by induction it holds for all positive integers \(n\).
MechanismDivisibility: make the assumption visible
Divisibility claims change the bookkeeping. Define \(f(n)\) as the expression — say \(f(n)=5^{2n}-1\) — and translate the hypothesis into an equation: '\(f(k)\) is divisible by \(24\)' becomes \(f(k)=24m\) for some integer \(m\). Naming that integer matters: 'divisible by 24' is a sentence, but \(24m\) is algebra you can substitute.
The inductive step then has one job: write \(f(k+1)\) in terms of \(f(k)\). Match the power structure first — if the powers climb by a factor of \(5^2=25\) each step, write \(f(k+1)=25\cdot 5^{2k}-1\) and force a \(25\big(5^{2k}-1\big)\) into existence, absorbing the correction term: \(f(k+1)=25f(k)+24\). Both pieces are multiples of \(24\), so the sum is. An equally valid route is to compute \(f(k+1)-f(k)\), show the difference is a multiple of the divisor, and add it back to the hypothesis — either way, the sentence that closes the step is 'a sum of multiples of \(24\) is a multiple of \(24\)'. What never earns marks is arithmetic on individual numbers: the step must be structural, true for every \(k\) simultaneously.
Prove that \(5^{2n}-1\) is divisible by \(24\) for all positive integers \(n\).
Basis: \(n=1\) gives \(5^2-1=24\), which is divisible by \(24\). Hypothesis: assume \(5^{2k}-1=24m\) for some positive integer \(k\) and integer \(m\). Step: \[5^{2(k+1)}-1=25\cdot 5^{2k}-1=25\big(5^{2k}-1\big)+25-1=25(24m)+24=24(25m+1),\] and \(25m+1\) is an integer, so \(5^{2(k+1)}-1\) is divisible by \(24\).
Conclusion: the result holds at \(n=1\) and is inherited from each \(k\) to \(k+1\), so by induction \(5^{2n}-1\) is divisible by \(24\) for every positive integer \(n\). (Sanity check: \(n=2\) gives \(624=24\times 26\).)
MechanismMatrix powers: all four entries must land
Matrix questions hand you a conjectured closed form and ask you to certify it: prove that \(\mathbf{M}^n\) equals some matrix whose entries are formulae in \(n\). The basis is the cheapest in the course — set \(n=1\) in the closed form and confirm it reads exactly \(\mathbf{M}\). The step is one matrix multiplication: \(\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}\), replace \(\mathbf{M}^k\) by the assumed form, multiply, and tidy every entry into the target — the closed form with \(k+1\) in place of \(n\). Write that target matrix down before multiplying, so each entry has somewhere to land.
Two details examiners watch. First, all four (or nine) entries must be resolved to the target shape; three correct entries and one abandoned \(-2k-1\) that is never shown to equal \(1-2(k+1)\) drops the accuracy mark. Second, powers of the same matrix commute — \(\mathbf{M}^k\mathbf{M}=\mathbf{M}\mathbf{M}^k\) — so either order is legitimate, but say which you are using and stick to it, because matrix multiplication in general does not commute. This leaf is also where the section quietly joins hands with the matrices topic: diagonalisation will generate closed forms for \(\mathbf{M}^n\); induction is the machine that proves them.
Let \(\mathbf{M}=\begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}\). Prove that \(\mathbf{M}^n=\begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix}\) for all positive integers \(n\).
Basis: \(n=1\) gives \(\begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}=\mathbf{M}\). Hypothesis: assume the form holds for \(n=k\). Step: \[\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}=\begin{pmatrix} 2k+1 & -4k \\ k & 1-2k \end{pmatrix}\begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}.\] Entry by entry: top-left \(3(2k+1)-4k=2k+3=2(k+1)+1\); top-right \(-4(2k+1)+4k=-4k-4=-4(k+1)\); bottom-left \(3k+(1-2k)=k+1\); bottom-right \(-4k-(1-2k)=-2k-1=1-2(k+1)\). So \(\mathbf{M}^{k+1}=\begin{pmatrix} 2(k+1)+1 & -4(k+1) \\ k+1 & 1-2(k+1) \end{pmatrix}\) — the claimed form with \(n=k+1\).
Conclusion: true at \(n=1\) and inherited from \(k\) to \(k+1\), so true for all positive integers \(n\) by induction.
CaseConjecture first, prove second
AQA's favourite packaging for this topic is a staged question: part (a) compute \(\mathbf{M}^2\) and \(\mathbf{M}^3\), part (b) 'write down a conjecture for \(\mathbf{M}^n\)', part (c) 'prove your conjecture by induction'. The structure is teaching you the epistemology. Parts (a) and (b) are Fermat's move — pattern-spotting, worth a couple of marks and carrying no certainty — while part (c) is the Euler-proofing. Before committing six marks to the proof, test your conjecture on the next unused case (\(n=3\) if you built it from \(n=1\) and \(2\)); thirty seconds there catches a wrong guess before you try to prove the unprovable.
Bases also move. A claim stated 'for all integers \(n\ge 0\)' starts the basis at \(n=0\); one stated 'for \(n\ge 2\)' starts at \(n=2\). The engine is untouched — only the anchor shifts, and the conclusion must quantify over exactly the set the question named. 'For all positive integers' and 'for all \(n\ge 0\)' are different theorems, and the final mark is paid for concluding precisely the one that was asked.
VocabularyKey terms the mark scheme pays for
TrapsMisconceptions that cost marks
ExamWhat examiners want
Induction lives in AO2 — 'reason, interpret and communicate mathematically' — which carries roughly a quarter of the marks on each Further Maths paper, and mark schemes track the four moves almost one-for-one: a mark for a basis where both sides are evaluated (not merely asserted equal), method for stating and then actually using the \(n=k\) assumption, accuracy for algebra that lands visibly on the \(k+1\) form, and a final mark reserved for the conclusion. That last mark has fixed ingredients: the basis, the implication, and the quantifier — 'true for \(n=1\), and true for \(n=k\) implies true for \(n=k+1\), so the result holds for all positive integers \(n\) by induction'.
The two wordings that cost most: 'assume \(n=k\)' (meaningless — you assume the statement holds when \(n=k\)) and 'assume the result is true for all \(n\)' (circular — the proof is over before it starts). In the step, never jump: the examiner must see \((k+1)\big[k(k+1)+3k+4\big]\) become \((k+1)(k+2)^2\), see the \(24(25m+1)\), see all four matrix entries resolved to their \(k+1\) forms. And if a staged question asked you to conjecture first, refer back to the conjecture in your conclusion — closing the loop is exactly the communication AO2 is buying.