Proof Methods: Induction¶
Induction is how you prove a statement holds for all natural numbers at once, without checking them one by one (which would never end). It's less a topic than a technique — but it's examined in its own right, almost always as a Part C problem where, as usual, the write-up is most of the mark.
The mental image. Induction is dominoes. If you show (1) the first domino falls, and (2) each domino knocks over the next, then you may conclude all of them fall — even though you never touched most of them. The two steps below are exactly those two promises.
The structure¶
Mathematical induction
To prove \(P(n)\) holds for all \(n \geq n_0\):
- Base case. Prove \(P(n_0)\) directly. (This is the first domino. \(n_0\) is usually \(0\) or \(1\) — use whatever value the claim actually starts at.)
- Inductive step. Assume \(P(k)\) holds for some \(k \geq n_0\) — this assumption is the induction hypothesis — and use it to prove \(P(k+1)\). (This is "each domino knocks over the next.")
Together these let you conclude \(P(n)\) for all \(n \geq n_0\).
The subtle point beginners distrust: in the inductive step you get to assume the very thing you're trying to prove — but only for \(k\), in order to establish it for \(k+1\). That's not circular, because the base case anchors the chain and the step only ever pushes one rung higher.
Strong induction is a variant where you assume \(P\) holds for all values up to \(k\) (not just \(k\) itself) when proving \(P(k+1)\). Reach for it when \(P(k+1)\) depends on more than the immediately preceding case — e.g. a sequence defined from the two previous terms.
How to write one up (this is where the marks are)¶
The exam grades presentation explicitly, and induction is where a sloppy write-up shows most. A full-marks proof makes four things impossible to miss:
- State the claim \(P(n)\) precisely, as a standalone statement about \(n\).
- Do the base case, and label it. It's one line; skipping it is a genuine logical gap (dominoes that all knock each other over but where none actually starts falling prove nothing).
- State the induction hypothesis explicitly — write out, in symbols, exactly what you're assuming.
- Mark the spot where you use it. Put an "I.H." over the equals sign, or say "by the induction hypothesis". This is the single line that turns your algebra into an actual induction proof.
The most common way induction proofs fail
Proving \(P(k+1)\) from scratch without ever using \(P(k)\). If the induction hypothesis is never invoked, then either the statement didn't need induction at all, or — far more likely — the argument is secretly circular and assumed what it set out to prove. Litmus test: point to the exact line where the hypothesis enters. If you can't, the proof is broken.
The standard shape for divisibility¶
The most common exam induction is a divisibility claim, and they all yield to the same move: in the inductive step, rewrite the \((k+1)\) expression to expose the \(k\) expression inside it, then substitute the hypothesis. Watch it happen:
Exam (May 2024, Problem 7): prove \(19 \mid 3^{3n-2} + 2^{3n+1}\)
Base case (\(n = 1\)). Plug in:
which is divisible by \(19\). First domino down. ✓
Induction hypothesis. Assume the claim at \(n = k\): \(19 \mid 3^{3k-2} + 2^{3k+1}\). The most useful form to write it in is as a congruence — rearranged so one term is expressed via the other:
Inductive step. Look at \(n = k+1\) and peel off the extra factors so the \(k\)-expression surfaces (note \(3^{3(k+1)-2} = 3^{3k-2}\cdot 3^3\) and \(2^{3(k+1)+1} = 2^{3k+1}\cdot 2^3\)):
So \(19 \mid 3^{3(k+1)-2} + 2^{3(k+1)+1}\), the claim at \(k+1\). By induction it holds for every positive integer \(n\). \(\square\)
Two transferable tricks:
- Turn the hypothesis into a congruence (\(2^{3k+1} \equiv -3^{3k-2}\)). "Divides" is hard to substitute; a congruence slots straight into an algebra chain.
- The substitution collapses two terms into one common factor (\(3^{3k-2}\)), and the leftover \((27 - 8) = 19\) finishes it. That "collapse to a common factor" is the mechanism you're steering toward every time.
Other standard targets¶
The extra-exercise sheets drill four shapes. All four use the same discipline — expose the \(k\)-case, apply the hypothesis, tidy up:
- Divisibility. e.g. \(4 \mid 5^n - 1\) for \(n \geq 0\), or \(3 \mid n^3 - n\) for \(n \geq 0\). Exactly the method above.
- Summation formulas. Split off the last term: \(\sum_{i=1}^{k+1} a_i = \big(\sum_{i=1}^{k} a_i\big) + a_{k+1}\). Apply the hypothesis to the bracket, then do algebra to match the target formula at \(k+1\).
- Inequalities. e.g. \(2^{n+1} > n + 2\) for \(n \geq 1\). Same skeleton, but you bound rather than substitute an equality — and you must track the direction of the inequality at every step.
- Binomial identities. e.g. \(\binom{2n}{n} = \frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}2^n\). Take the ratio of consecutive terms; the inductive step becomes a small cancellation.
Worked slowly: \(4 \mid 5^n - 1\)
Base case (\(n = 0\)). \(5^0 - 1 = 1 - 1 = 0\), and \(4 \mid 0\) (zero is divisible by everything). ✓
Hypothesis. Assume \(4 \mid 5^k - 1\), i.e. \(5^k \equiv 1 \pmod 4\).
Step. Expose \(5^k\) inside \(5^{k+1}\), then substitute:
So \(4 \mid 5^{k+1} - 1\), completing the induction. Same three beats every time: expose, substitute, collapse.