What Is Mathematical Induction? Proving Infinitely Many Things at Once

The method has two parts. The base case establishes the statement for a starting value, usually the first one of interest. The inductive step establishes that if the statement holds for an arbitrary value, it holds for the next one, which is a conditional claim proved once and applying everywhere. Together these give the conclusion, because the base case delivers the first, the step carries it to the second, the step again carries it to the third, and nothing can escape, since any particular case is reached in finitely many moves from the start. The standard image is a line of dominoes, where knocking the first over and knowing that each knocks over its neighbour is enough to conclude that all of them fall, without checking any individually beyond the first.

The method is mechanical and the failures are identifiable:

• •Omitting the base case, which leaves a chain with nothing to start it and permits proving false statements
• •Assuming what is to be proved rather than assuming it for one value and deriving it for the next
• •An inductive step that fails for small values, which is the flaw in the famous argument that all horses are the same colour
• •Applying it to a statement about real numbers rather than whole numbers, where it does not apply
• •Proving the wrong conditional, establishing that the next case implies the current one
• •Losing track of what the arbitrary value stands for, which is where careless proofs usually collapse

Variants exist because the basic form is sometimes insufficient. Strong induction assumes the statement for all values up to a point rather than only for the immediately preceding one, which is necessary when a case depends on several earlier cases rather than just the last, and it is used constantly in results about factorisation and about recursive structures. Structural induction extends the method beyond numbers to any structure built up by rules, which is how properties of trees, lists, formulas and programs are proved. Transfinite induction extends it past the finite numbers entirely. The well-ordering principle, that every non-empty set of positive whole numbers has a least element, turns out to be equivalent to the induction principle, and a proof by induction can generally be rewritten as an argument taking a smallest counterexample and deriving a contradiction.

The method suits particular kinds of statement and recognising them saves effort. Formulas for the sum of a sequence are the classic case, since the sum to a given point relates directly to the sum to the point before. Divisibility claims work well, since establishing that a difference is divisible carries the property forward. Inequalities holding for all whole numbers beyond some point are standard. Statements about structures built recursively, including trees, nested expressions and programs, are proved by the structural version constantly, and the correctness of a recursive algorithm is generally established this way. Counting arguments about arrangements frequently reduce to a recurrence and then to an induction. What the method does not do is find the statement in the first place, since it verifies a formula rather than deriving one, and the creative work of guessing the right general statement remains separate.

The method is deductive despite being called induction, and the clash of terms causes real confusion. Induction in the ordinary and philosophical sense means generalising from observed instances to a conclusion that goes beyond them, which is not a valid deduction and is the subject of a famous philosophical problem. Mathematical induction proves a general statement with certainty from two established facts, which is a valid deduction and carries no risk of the conclusion failing. Nothing is being generalised from examples, since the inductive step is proved for an arbitrary case rather than checked for several. The shared name is a historical accident. The practical consequence is that a student who understands the method as generalising from a few cases has misunderstood it, and that misunderstanding is exactly what produces the common error of checking a few values and declaring the result proved.

A base case plus a proof that each case implies the next establishes every case, since any particular one is reached in finitely many steps. Omitting the base case permits proving false things, and an inductive step that fails at small values is the flaw in the all-horses argument. Despite the name, the method is deductive and proves with certainty, generalising from nothing.