Contradiction and induction

A tower of n disks sits on one of three pegs, and the task is to move the whole tower to another peg without ever placing a larger disk on a smaller one. The largest disk cannot move until everything above it has moved away, so the problem reduces to transferring a tower of n−1 disks twice and then moving the largest disk once. Write T(n) for the number of moves the task needs with n disks; then T(n) = 2T(n−1) + 1, with T(0) = 0 because an empty tower already sits where it belongs [S:1:44]. The first values are 0, 1, 3, 7, 15 and 31, the formula 2ⁿ − 1 generates an identical list, and six coincidences are still not a proof, however suggestive the pattern appears.

Induction is the argument that carries such a list to every n, and it answers this section's question in two parts. An induction proof has two jobs: establish the claim at the first case, and show that any case forces the next one. The first job is the base case. The second is the inductive step, and it is a conditional claim: "if the case at n holds then the case at n+1 holds". !A first failure would need a success immediately below it, and the step forbids that. The base case holds at the first rung, so the first failure is not there. Suppose the claim fails somewhere, and let $m$ be the first place it fails: every case below $m$ holds, so the case at $m-1$ holds, and the step carries the case at $m-1$ to the case at $m$. The arrow and the shaded failure cannot both stand. The ellipsis keeps the line from ending, so no case is the last one the argument reaches. Status: schematic.

The conventional image is a row of dominoes, where the first falls and each falling domino knocks over the next. The image breaks in one specific place: a row of dominoes is finite and physical, while the whole numbers have no final domino whose fall could be inspected.

Worked example. Show that 1 + 2 + … + n = n(n+1)/2 for every whole number n.

At n = 0 the left side is a sum of no terms, which is 0 by the convention that adding nothing changes nothing, and the right side is 0 × 1/2 = 0, so the base case holds. For the step, assume the claim at n. That assumption is not something you have proved; it is the hypothesis of the conditional you are about to prove, and it is discharged when the conditional is finished. Add the next whole number to both sides:

That line says the sum up to n+1 is the sum up to n plus one additional term, and the right side collapses to the formula at n+1. The case at n therefore forces the case at n+1, for every n; at n = 4 the sum is 1 + 2 + 3 + 4 = 10, and 4 × 5/2 = 10.

The two obligations together cover every case, and the reason deserves a slow statement. Suppose that some index, one of the whole numbers used to label the cases, fails. Take the smallest index at which the claim fails. It cannot be 0, because the base case holds there.

The index below it is smaller, so the claim holds there, and the step says the claim holds at the next one, which is the failing index. That is a contradiction, so no index fails, and the checked values were never the substance of the exercise.

The other route. Contradiction assumes that the claim is false and derives an impossibility from that assumption, and it earns its place when the assumption hands you an object to work with. The standard case is the square root of 2, assumed to be a fraction in lowest terms [S:16:152]. Write it p/q, with p and q whole numbers that share no factor; then p² = 2q², so p² is even, so p is even and equals 2r.

Substituting gives 4r² = 2q², so q² = 2r², and q is even as well. Both numbers are even, which contradicts the supposition that they share no factor, so no such fraction exists. Observe what the assumption purchased: two whole numbers with names, and a sentence about them that can be checked. That is when this route is the less expensive one: the negation hands you an object, and arithmetic on the object closes the argument.

Occasionally the step needs more than the case immediately below it. Strong induction permits the assumption of every earlier case, and it is the instrument to reach for when the case at n+1 depends on smaller cases of unknown size [S:5:132]. The generalisation is mechanical bookkeeping: the smallest failing index argument above runs unchanged, because the index below the smallest failure is smaller still.

Induction verifies and does not explain, and the source is blunt about it: induction, by definition, can be used only to verify results conjectured by other means [S:22:20]. The formula for the sum was discovered before it was proved: pair the first term with the last, the second with the second last, and each pair sums to n+1. The odd case leaves a middle term unpaired, which is (n+1)/2, and that discovery is separate work that induction did not supply.

Contradiction has its own cost. It establishes that a supposition fails, and it does not hand you the object that makes the claim true: a proof by contradiction of an existential claim tells you that something exists, not what it is.

Induction also reaches only claims indexed by whole numbers. A claim about all real numbers needs a reduction to that index first, a step that converts the real-number claim into a statement about a whole-number parameter. Where that step is unavailable, the generalisation to the real line needs a continuity argument. A continuity argument uses the fact that a quantity changing without a jump cannot pass from one value to another without taking every value between, and this chapter does not develop one.

The formal statement. Let the sentence about a whole number $n$ be true or false at each $n$, and write it $S(n)$. Induction says: if the sentence holds at 0, and if the sentence at $n$ implies the sentence at $n+1$ for every $n$, then it holds at every $n$. In one line,

The display says: a first case plus a step that carries any case to its successor covers every case.

The derivation. Induction is equivalent to well-ordering, the statement that every nonempty collection of whole numbers has a least member. Assume well-ordering and suppose the two hypotheses hold while the conclusion fails. Let $F$ be the collection of whole numbers at which the sentence fails. It is nonempty, so it has a least member $m$. The base case rules out $m=0$, so $m-1$ is a whole number. Since $m$ is least, the sentence holds at $m-1$, and the step gives it at $m$, contradicting the definition of $F$. So no failure exists.

The omitted direction runs the same argument backwards. The two are equivalent, so neither is derived from nothing: one is an axiom of the whole numbers.

Strong induction. Assume that for every $n$, the sentence at $n$ follows from all the cases below $n$. Then it holds at every $n$. The failure-set argument is unchanged. Ordinary induction uses only the case at $n-1$. Use the strong form when the case at $n$ splits into smaller cases, as when a whole number above 1 factors.

The edge case. The Tower of Hanoi recurrence is usually read as one bound. The algorithm moves $n-1$ disks aside, moves the largest once, and moves $n-1$ back, so the count obeys $T(n)=2T(n-1)+1$ with $T(0)=0$, and induction gives $T(n)=2^n-1$ [S:1:44]. That equality hides two claims. The algorithm gives an upper bound. The lower bound needs a separate argument: before the largest disk moves, all smaller disks must be off it, and afterwards all must be stacked on it, so no strategy beats the recurrence. The core's "therefore" compressed both bounds into one line.

The edge case of the first rung. A step that uses two earlier cases needs two base cases. The Fibonacci bound is the example: its step at $n+2$ uses the cases at $n$ and $n+1$, so a single base case leaves the second rung unproved. The horse argument of 3.6 fails in the same place: its step silently requires $n$ from two upwards, and the chain never starts.

Where the dominoes analogy breaks. Dominoes suggest a sequence of events in time, each case inspected after the one below it. Induction is one implication, proved once, and it mentions no process. The image also misplaces the start: induction may begin at any integer, and the base case is whatever rung the step needs.

What the core left out. The induction hypothesis is an assumption inside a conditional, not a fact that you have established. The core's "assume the claim at $n$" invites the reading that you assume what you want to prove. You prove one conditional, and the assumption is discharged with it.

Original sources. The staircase statement of the principle, with the induction assumption named, is section 1.2 of Trench [S:22:20]. The Tower of Hanoi recurrence, its base case and the induction that solves it are section 1.1 of Erickson [S:1:44]. Strong induction, and the horses argument that fails, are sections 5.1 and 5.2 of Mathematics for Computer Science [S:5:132].

An open question. Induction checks a claim; it does not find one. Trench states the point without hedging: induction can be used only to verify results conjectured by other means [S:22:20]. The open question is whether a machine can supply the missing step, which is the choice of what to prove. Given a statement, a prover must decide whether to strengthen it, and by how much. Nothing in the method says how to find the strengthening. Evidence that would settle the question: a system that receives only a statement, with no human-supplied lemma, and produces the strengthened claim and its proof, scored on problems whose published solutions require a generalisation. A high score on problems that already carry their lemmas would not settle it.

A frontier result. DeepSeek-Prover-V2 decomposes a theorem into subgoals and proves the subgoals recursively, which is the machine version of choosing an intermediate claim [S:604:1]. It reaches 88.9% on the MiniF2F test set and solves 47 of 658 problems from PutnamBench [S:604:1]. The first benchmark is Olympiad-level and the second is undergraduate mathematics, so the same machinery meets a harder test and clears far less of it.

What to read next. Read section 1.2 of [S:22:20] for the principle and its warning, and section 1.1 of [S:1:44] for a recurrence proved by induction. Read chapter 5 of [S:5:132] for strong induction and for a step that fails at its first rung. Read [S:604:1] for the subgoal decomposition that the classical texts leave to the reader.