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:

\[ 3^{3(1)-2} + 2^{3(1)+1} = 3^{1} + 2^{4} = 3 + 16 = 19, \]

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:

\[ 2^{3k+1} \equiv -3^{3k-2} \pmod{19} \]

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\)):

\[ \begin{aligned} 3^{3(k+1)-2} + 2^{3(k+1)+1} &= 3^{3k-2} \cdot 3^3 + 2^{3k+1} \cdot 2^3 \\ &\stackrel{\text{I.H.}}{\equiv} 3^{3k-2} \cdot 3^3 - 3^{3k-2} \cdot 2^3 \pmod{19} &&\text{(replaced } 2^{3k+1} \text{ using the hypothesis)}\\ &= 3^{3k-2}\,(27 - 8) \\ &= 3^{3k-2} \cdot 19 \\ &\equiv 0 \pmod{19}. \end{aligned} \]

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:

\[ 5^{k+1} - 1 = 5 \cdot 5^k - 1 \stackrel{\text{I.H.}}{\equiv} 5 \cdot 1 - 1 = 4 \equiv 0 \pmod 4. \]

So \(4 \mid 5^{k+1} - 1\), completing the induction. Same three beats every time: expose, substitute, collapse.

A summation, fully worked¶

Summation proofs use the same skeleton, but the key move is splitting off the last term so the \(k\)-sum appears, ready for the hypothesis.

Worked slowly: \(\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}\)

Claim \(P(n)\): \(\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\).

Base case (\(n = 1\)). Left side \(= 1\); right side \(= \frac{1\cdot 2}{2} = 1\). Equal. ✓

Induction hypothesis. Assume \(\displaystyle\sum_{i=1}^{k} i = \frac{k(k+1)}{2}\).

Inductive step. Split the last term off the \((k+1)\)-sum, then substitute the hypothesis:

\[ \sum_{i=1}^{k+1} i = \underbrace{\sum_{i=1}^{k} i}_{\text{apply I.H.}} + (k+1) \stackrel{\text{I.H.}}{=} \frac{k(k+1)}{2} + (k+1). \]

Now it's pure algebra — factor out \((k+1)\) and aim for the target shape \(\frac{(k+1)(k+2)}{2}\):

\[ \frac{k(k+1)}{2} + (k+1) = (k+1)\!\left(\frac{k}{2} + 1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}. \]

That is exactly \(P(k+1)\). By induction the formula holds for all \(n \geq 1\). \(\square\)

An inequality, fully worked¶

Inequalities follow the same beats with one change: in the step you bound rather than substitute an equality, and you must watch the direction of the inequality the whole way.

Worked slowly: \(2^n > n^2\) for \(n \geq 5\)

Claim \(P(n)\): \(2^n > n^2\), for \(n \geq 5\).

Base case (\(n = 5\)). \(2^5 = 32 > 25 = 5^2\). ✓ (Note it fails at \(n=4\): \(16 = 16\). The base case has to start where the claim first becomes true — picking \(n_0 = 5\) is part of getting it right.)

Induction hypothesis. Assume \(2^k > k^2\) for some \(k \geq 5\).

Inductive step. Expose \(2^k\), apply the hypothesis, then bound the rest:

\[ 2^{k+1} = 2\cdot 2^k \stackrel{\text{I.H.}}{>} 2k^2. \]

It now suffices to show \(2k^2 \geq (k+1)^2\), because then \(2^{k+1} > 2k^2 \geq (k+1)^2\). Rearranging, \(2k^2 \geq (k+1)^2\) means \(k^2 - 2k - 1 \geq 0\), i.e. \(k \geq 1+\sqrt 2 \approx 2.41\) — comfortably true for \(k \geq 5\). Chaining the two:

\[ 2^{k+1} > 2k^2 \geq (k+1)^2, \]

which is \(P(k+1)\). By induction, \(2^n > n^2\) for all \(n \geq 5\). \(\square\)

The extra obligation inequalities carry

The hypothesis only got you to \(2k^2\); a second inequality (\(2k^2 \geq (k+1)^2\)) bridged the gap to the target. Budget for that: an induction inequality often needs a small side-argument that the bound you produced is itself big enough. State it explicitly.

Strong induction in action¶

Strong induction assumes \(P\) for all values up to \(k\), not just \(k\) itself. Reach for it when the step naturally refers to a case further back than the immediate predecessor — and the classic example is a statement about factoring, where the pieces are smaller but you can't predict how much smaller.

Worked slowly: every integer \(n \geq 2\) is a product of primes

Claim \(P(n)\): \(n\) can be written as a product of one or more primes.

Base case (\(n = 2\)). \(2\) is prime, so it's a product of one prime (itself). ✓

Strong induction hypothesis. Assume \(P(j)\) holds for every \(j\) with \(2 \leq j \leq k\) — i.e. every integer from \(2\) up to \(k\) factors into primes.

Inductive step. Consider \(k+1\). Two cases:

If \(k+1\) is prime, it's a product of one prime — done.
If \(k+1\) is composite, then \(k+1 = a\cdot b\) with \(2 \leq a, b \leq k\). Here's where strong induction is essential: \(a\) and \(b\) are both in the range covered by the hypothesis, so each factors into primes. Concatenating those two prime factorisations gives one for \(k+1\). ✓

Either way \(P(k+1)\) holds, so by strong induction every integer \(n \geq 2\) is a product of primes. \(\square\)

Why ordinary induction won't do here. The step used \(P(a)\) and \(P(b)\) for factors that can sit anywhere below \(k+1\), not at \(k\). Ordinary induction only hands you \(P(k)\) — useless when the factors are, say, \(3\) and \(7\) for \(k+1 = 21\). Whenever the step reaches back an unpredictable distance, that is the signal for strong induction.