Mathematical induction

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

The most common form of proof by mathematical induction requires proving in the induction step that

A variant of interest in computational complexity is "prefix induction", in which one proves the following statement in the induction step:

Complete induction is most useful when several instances of the inductive hypothesis are required for each induction step. For example, complete induction can be used to show that

However, there will be slight differences in the structure and the assumptions of the proof, starting with the extended base case.

The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with the following four other axioms:

A may be read as a set representing a proposition, and containing natural numbers, for which the proposition holds. This is not an axiom, but a theorem, given that natural numbers are defined in the language of ZFC set theory by axioms, analogous to Peano's.

It can then be proved that induction, given the above-listed axioms, implies the well-ordering principle. The following proof uses complete induction and the first and fourth axioms.