Appearance
8.3 — Proof and Induction
Check the expression n^2 + n + 41 for n = 0, 1, 2, \ldots Every value you get is prime. 41, 43, 47, 53, 61, 71, 83, 97, 113. Keep going and it stays prime for forty consecutive values.
It fails at n = 40, where the value is 41^2, divisible by 41.
Forty confirmations proved nothing. This is why mathematics does not accept evidence, however much of it there is. A proof is a demonstration that something holds in every case, including the cases nobody has checked and the infinitely many nobody could.
Chapter 3.1 introduced proof; this chapter covers the standard shapes an argument takes.
1. Direct proof
Assume the hypothesis and reason to the conclusion.
Claim: the sum of two even numbers is even.
Let a and b be even. By definition that means a = 2m and b = 2n for some integers m,n. Then
a+b = 2m+2n = 2(m+n)
which is 2 times an integer, so it is even. \blacksquare
The filled square marks the end of a proof, a convention introduced by Paul Halmos and called a tombstone.
Notice the structure. Unpack the definitions, do algebra, repack into the definition of what you wanted. Most direct proofs look exactly like this, and "write down what the words actually mean" is the first move in almost every one.
Claim: if n is odd then n^2 is odd.
n = 2k+1, so n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1, which is odd. \blacksquare
2. Proof by contraposition
To prove P\to Q, prove \neg Q\to\neg P instead. Chapter 8.2 established these are logically identical.
Claim: if n^2 is even then n is even.
Direct attack is awkward — knowing n^2 = 2k tells you little about n. So prove the contrapositive: if n is odd then n^2 is odd. That is Section 1's second result, already done. \blacksquare
When to reach for it: when the hypothesis is hard to use and the negated conclusion is easy to use. Chapter 1.7's irrationality proof used exactly this step, when it needed "a^2 even implies a even".
3. Proof by contradiction
Assume the opposite of what you want and derive an impossibility.
Chapter 1.7's proof that \sqrt2 is irrational is the model: assume it is a fraction in lowest terms, deduce that both parts are even, contradict "lowest terms".
Chapter 1.5's proof that there are infinitely many primes is another: assume finitely many, build a number none of them divides, contradiction.
Another one, short and pleasing. Claim: there is no smallest positive rational number.
Suppose r is the smallest. Then \frac{r}{2} is positive, rational, and smaller. Contradiction. \blacksquare
A caution. Contradiction is powerful and often over-used. A proof that assumes the negation, derives the result directly, and then says "which contradicts our assumption" is a direct proof wearing a costume. Use contradiction when the negation genuinely gives you something to work with — as "assume it is a fraction" does.
4. Proof by cases
Split into exhaustive possibilities and prove each.
Claim: n^2+n is even for every integer n.
Case 1: n even. Then n^2 is even and n is even, so the sum is even. Case 2: n odd. Then n^2 is odd and n is odd, and odd plus odd is even.
Both cases hold and they cover everything. \blacksquare
(A slicker argument: n^2+n = n(n+1), the product of consecutive integers, one of which must be even. Shorter proofs usually exist and finding them is a skill, but a correct clumsy proof is worth more than an elegant wrong one.)
The four colour theorem of Chapter 3.6 is proof by cases at industrial scale — 1,936 cases, checked by computer. It works, and it started a genuine argument about whether a proof no human can read is a proof at all.
5. Proof by counterexample
To disprove a universal claim, exhibit one failure. Chapter 8.2 gave the logical basis: the negation of "for all x, P(x)" is "there exists an x with not P(x)".
Claim: every odd number is prime. Counterexample: 9. \blacksquare
Claim: n^2+n+41 is always prime. Counterexample: n=40. \blacksquare
One counterexample kills a universal claim completely. No number of confirming instances establishes one. This asymmetry is the same one Karl Popper built a philosophy of science on: theories can be falsified by a single observation and never verified by any number of them.
Two conjectures that failed after a very long time
Pólya's conjecture (1919) claimed that up to any number n, at least half the integers have an odd number of prime factors. Verified extensively. The smallest counterexample is n = 906{,}150{,}257, found in 1980.
The Mertens conjecture was disproved in 1985, and the smallest counterexample is known to be somewhere below 10^{10^{40}} — a number with more digits than the universe has atoms. It will never be exhibited. The disproof shows one must exist without producing it.
If a pattern holding for a billion cases can fail, testing is not proof. This is exactly why software testing finds bugs and cannot establish correctness, which Volume I, 1.7 discusses from the computing side.
6. Mathematical induction
The technique for proving something about all natural numbers.
The principle. To prove P(n) for every n \ge 1:
- Base case. Show P(1) is true.
- Inductive step. Show that if P(k) is true then P(k+1) is true.
Then P(n) holds for every n.
Why this works. The base gives you P(1). The step turns P(1) into P(2), then P(2) into P(3), forever. Every natural number is reached by finitely many applications.
The domino picture: knock over the first, and ensure each one topples the next, and the whole infinite line falls. Both parts are essential — dominoes correctly spaced but never pushed do not fall, and a pushed first domino too far from the second stops immediately.
Worked example. Prove 1+2+\cdots+n = \frac{n(n+1)}{2}.
Base: n=1. Left side is 1, right side is \frac{1\times2}{2} = 1. ✓
Step: assume it holds for k, so 1+\cdots+k = \frac{k(k+1)}{2}. Then
1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = (k+1)\left(\frac k2+1\right) = \frac{(k+1)(k+2)}{2}
which is the formula with k+1 in place of n. ✓ \blacksquare
The story attached to this formula: Gauss's schoolteacher supposedly set the class to add 1 to 100 as busywork, and Gauss produced 5,050 within seconds by pairing 1 with 100, 2 with 99, and so on — fifty pairs each summing to 101. The anecdote's details are unreliable, and the pairing argument is a genuine and better proof than induction here, because it explains why rather than merely verifying.
That distinction is worth holding onto. Induction verifies; it rarely explains. If you already suspect a formula, induction confirms it. It will not tell you where the formula came from.
Worked example with an inequality. Prove 2^n \gt n for all n\ge1.
Base: 2^1 = 2 \gt 1. ✓ Step: assume 2^k \gt k. Then 2^{k+1} = 2\cdot2^k \gt 2k = k + k \ge k+1 whenever k \ge 1. ✓ \blacksquare
Strong induction
Sometimes P(k) alone is not enough and you need every case below k.
Assume P(1), P(2), \ldots, P(k) all hold, and prove P(k+1).
Chapter 1.5's proof that every integer has a prime factorisation used this: n = ab with both factors smaller than n, and you need the result for both of them, not just for n-1.
Strong induction and ordinary induction are logically equivalent, and strong induction is often the natural fit for anything involving splitting a problem into smaller pieces — which is exactly the shape of divide-and-conquer algorithms.
A famous fake proof
Claim: all horses are the same colour.
Base: one horse. Trivially the same colour as itself. ✓
Step: assume any k horses are the same colour. Take k+1 horses. The first k are all one colour by assumption. The last k are all one colour by assumption. The two groups overlap, so all k+1 share that colour. ✓
The conclusion is false, so the proof is wrong. Where?
At k=1. Going from 1 to 2 horses, the "first 1" is horse A and the "last 1" is horse B, and the two groups do not overlap. The argument silently assumes k \ge 2, so the chain never starts.
The lesson: check that the inductive step works at the very first value, not just in general. A step that fails once breaks the whole chain, and this is the most common real error in inductive proofs.
7. Induction in computing
Recursion is induction. A recursive function has a base case and a step that reduces to smaller inputs, which is exactly the structure above. Proving a recursive function correct is an induction, and Volume I, 4.9 develops the algorithmic side.
Loop invariants. To prove a loop correct, find a property that holds before the loop starts, is preserved by each iteration, and gives the desired result when the loop ends. That is induction on the iteration count. It is how algorithms are actually verified, and it is what a formal-methods tool checks.
Structural induction generalises to trees and other recursive structures: prove it for leaves, then prove that if it holds for a node's children it holds for the node. Every proof about a binary tree, a parsed expression, or a nested data structure has this shape.
Recurrence relations. Analysing an algorithm's cost gives an equation like T(n) = 2T(n/2)+n, solved in Chapter 8.5 and used throughout Volume I, 4.1.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
The proof patterns
Direct. Assume p, deduce q by legal steps.
By contrapositive. To prove p\to q, prove \lnot q\to\lnot p instead. Use it when the negations are easier to work with — proving "if n^2 is even then n is even" is awkward directly and immediate in reverse, since an odd n = 2k+1 gives n^2 = 4k^2+4k+1, plainly odd.
By contradiction. Assume the statement is false, derive something impossible. This is how 1.P proved \sqrt3 irrational and how Euclid proved the primes never run out.
By cases. Split into possibilities that cover everything, prove each. Fine, provided the cases really are exhaustive.
By induction.
\text{If } P(1) \text{ and } \left[P(k)\Rightarrow P(k+1)\right], \text{ then } P(n) \text{ for all } n\ge1
Why it is valid. Suppose the conclusion failed. Then some smallest n has P(n) false. It cannot be 1, since P(1) was proved. So n-1\ge1 exists, and being smaller, P(n-1) is true — but the inductive step then forces P(n) to be true as well. Contradiction. Induction is guaranteed by the fact that any non-empty set of positive whole numbers has a smallest member.
Strong induction assumes P(1) through P(k) to prove P(k+1). Same principle, more assumed. Use it when a step depends on more than just the previous case — the proof that every number has a prime factorisation needs it, since factoring n produces two smaller numbers, not n-1.
The pigeonhole principle.
n \text{ items in } m \text{ boxes with } n>m \;\Rightarrow\; \text{some box has} \ge 2
\text{Generally, some box has at least } \left\lceil\frac nm\right\rceil
It sounds too obvious to be useful and it proves surprising things. Among any 13 people, two share a birth month. In London, at least two people have exactly the same number of hairs on their head — a head holds at most about 150,000 hairs, and there are nine million Londoners.
8. Where this shows up in your life
Every argument where you claim something always happens. The habit of asking "what would a counterexample look like?" is the single most useful transfer from this chapter.
Every recursive function you write, and the base case that stops it running forever.
Every piece of safety-critical software verified by loop invariants and theorem provers.
Every legal or policy argument. Cases, contrapositives and counterexamples are how such arguments are actually built and attacked.
Every "it works on all the examples I tried" claim — and the n^2+n+41 warning at the top of this chapter.
Proof gives certainty. The next chapter returns to structure: relations and functions, which are how mathematics describes one thing depending on another.