Mathematical induction
from 1575 Maurolico's explicit use; Pascal gives the first clear statement in 1654
Prove the first case, prove that any case carries the next, and you have proved infinitely many with two pieces of work.
- Active
- from 1575
- Where
- Sicily, later Paris
- Status
- In use
- Tradition
- Forms of inference
What it is
Despite the name, this is deduction and not induction at all. It establishes a claim about every natural number by proving two things: that it holds for the first, and that whenever it holds for one it holds for the next.
From those two the conclusion follows with full necessity for infinitely many cases. There is no probability and no generalisation from samples anywhere in it, which is why sharing a name with the empirical method is one of the more unfortunate accidents in the vocabulary.
How it works
Prove the base case. Assume the claim holds at some arbitrary n — the inductive hypothesis — and prove that it therefore holds at n plus one. Conclude that it holds for all n.
The second step is where the work is, and the assumption in it is not a leap of faith. You are not assuming the claim is true; you are proving a conditional, that if it holds anywhere it holds one step further on.
The form of the inference
- The claim holds for the first case
- If the claim holds for case n, then it holds for case n plus one
- Every case is reached from the first by finitely many such steps
- Therefore the claim holds for every case
The argument
Proposition Any straight run of fence, however long, can be built by one person working alone.
- One panel can be built alone: the post is set, the panel is hung against it, and nothing needs holding.
- Suppose a run of n panels has been built alone, which leaves a finished post standing at the far end.
- The next panel is hung against that standing post exactly as the first was hung against the first post, and requires nothing the first did not.
- So if a run of n can be built alone, a run of n plus one can be built alone.
Therefore A run of any length can be built by one person working alone.
The conclusion covers runs nobody will ever build, and it is proved without building any of them. That reach from two finite pieces of work to an infinity of cases is what the method is for.
What it is good for
Anything defined recursively or built in steps: sums, sequences, the correctness of loops in programs, and any structure where each case is made from the one before.
Where it fails
It fails when the inductive step is not uniform. If the move from n to n plus one depends on something that holds for small n and quietly stops holding for large n, the proof is broken and the break can be very hard to see — the classic bogus proof that all horses are the same colour fails at exactly one value of n and nowhere else.
It also cannot reach beyond the well-ordered. It works on the natural numbers because every one of them is finitely many steps from the first, and it requires a different and stronger apparatus, transfinite induction, to go further.
Common misconceptions
That it is a form of empirical induction, which it is not, and that the inductive hypothesis assumes what is to be proved, which it does not. The hypothesis is the antecedent of a conditional being proved, not a premise being granted.
Where it came from
Francesco Maurolico uses it explicitly in 1575. Pascal gives the first clear general statement in the Traité du triangle arithmétique of 1654. The underlying idea appears earlier in Indian and Islamic mathematics, in al-Karaji among others.
What became of it
Made foundational by Peano in 1889, who took it as one of the axioms defining the natural numbers rather than a result to be proved.
Lasting influence
Every proof about sequences, series, recursive structures and program correctness. It is also the reason computer science and mathematics share a proof technique.
Why it still matters
Central to mathematics and to formal verification of software.
Put another way
A row of dominoes. Tip the first, guarantee that each knocks its neighbour, and you need not watch the rest.
Texts
Giuseppe Peano, Arithmetices principia
Where induction stops being a technique and becomes an axiom defining what the natural numbers are.
Where to start
Prove that the first n whole numbers sum to n(n+1)/2. It is the standard first exercise because the base case and the step are both short and the shape is unmistakable.
The surprising bit
It carries the name of the least certain form of reasoning on this list while being among the most certain, and the collision of names has confused students for three centuries.
In their own words
What is true for one, and what is true for the next whenever it is true for one, is true for all
Who held it
Francesco Maurolico, al-Karaji
Connections
The verdict
A small, exact machine that produces infinitely many conclusions from two finite proofs.