Mathematical induction

A proof by induction consists of two cases. The first, the base case, proves the statement for ${\displaystyle n=0}$ without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case ${\displaystyle n=k}$, then it must also hold for the next case ${\displaystyle n=k+1}$. These two steps establish that the statement holds for every natural number ${\displaystyle n}$. The base case does not necessarily begin with ${\displaystyle n=0}$, but often with ${\displaystyle n=1}$, and possibly with any fixed natural number ${\displaystyle n=N}$, establishing the truth of the statement for all natural numbers ${\displaystyle n\geq N}$.


The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and is the foundation of most correctness proofs for computer programs.^[3]


Despite its name, mathematical induction differs fundamentally from inductive reasoning as used in philosophy, in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of deductive reasoning involving the variable ${\displaystyle n}$, which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.^[4]

The principle of mathematical induction is usually stated as an axiom of the natural numbers; see Peano axioms. It is strictly stronger than the well-ordering principle in the context of the other Peano axioms. Suppose the following:


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.


Proof. Suppose there exists a non-empty set, S, of natural numbers that has no least element. Let P(n) be the assertion that n is not in S. Then P(0) is true, for if it were false then 0 is the least element of S. Furthermore, let n be a natural number, and suppose P(m) is true for all natural numbers m less than n + 1. Then if P(n + 1) is false n + 1 is in S, thus being a minimal element in S, a contradiction. Thus P(n + 1) is true. Therefore, by the complete induction principle, P(n) holds for all natural numbers n; so S is empty, a contradiction. Q.E.D.


On the other hand, the set ${\displaystyle \{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}}$, shown in the picture, is well-ordered^[24]: 35lf by the lexicographic order. Moreover, except for the induction axiom, it satisfies all Peano axioms, where Peano's constant 0 is interpreted as the pair (0, 0), and Peano's successor function is defined on pairs by succ(x, n) = (x, n + 1) for all ${\displaystyle x\in \{0,1\}}$ and ${\displaystyle n\in \mathbb {N} }$. As an example for the violation of the induction axiom, define the predicate P(x, n) as (x, n) = (0, 0) or (x, n) = succ(y, m) for some ${\displaystyle y\in \{0,1\}}$ and ${\displaystyle m\in \mathbb {N} }$. Then the base case P(0, 0) is trivially true, and so is the induction step: if P(x, n), then P(succ(x, n)). However, P is not true for all pairs in the set.


Peano's axioms with the induction principle uniquely model the natural numbers. Replacing the induction principle with the well-ordering principle allows for more exotic models that fulfill all the axioms.^[24]


It is mistakenly printed in several books^[24] and sources that the well-ordering principle is equivalent to the induction axiom. In the context of the other Peano axioms, this is not the case, but in the context of other axioms, they are equivalent;^[24] specifically, the well-ordering principle implies the induction axiom in the context of the first two above listed axioms and


A common mistake in many erroneous proofs is to assume that n − 1 is a unique and well-defined natural number, a property which is not implied by the other Peano axioms.^[24]