The principle of finite induction, also known as mathematical induction, is commonly formulated in two ways. Both are equivalent. The first formulation is known as weak induction. It asserts that if a statement $P(n)$ holds for $n=0$ and if $P(n)\Rightarrow P(n+1)$ , then $P(n)$ holds for all natural numbers $n$ . The case $n=0$ is called the base case or base step and the implication $P(n)\Rightarrow P(n+1)$ is called the inductive step. In an inductive proof, one uses the term induction hypothesis or inductive hypothesis to refer back to the statement $P(n)$ when one is trying to prove $P(n+1)$ from it.

The second formulation is known as strong or complete induction. It asserts that if the implication $\forall n((\forall m < n P(m))\Rightarrow P(n))$ is true, then $P(n)$ is true for all natural numbers $n$ . (Here, the quantifiers range over all natural numbers.) As we have formulated it, strong induction does not require a separate base case. Note that the implication $\forall n((\forall m < n P(m))\Rightarrow P(n)$ already entails $P(0)$ since the statement $\forall m<0 P(m)$ holds vacuously (there are no natural numbers less that zero).

A moment's thought will show that the first formulation (weak induction) is equivalent to the following:

Let $S$ be a set natural numbers such that

1. $0$ belongs to $S$ , and
2. if $n$ belongs to $S$ , so does $n+1$ .

Then $S$ is the set of all natural numbers.

Similarly, strong induction can be stated:

If $S$ is a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$ , then $S$ is the set of all natural numbers.

The principle of finite induction can be derived from the fact that every nonempty set of natural numbers has a smallest element. This fact is known as the well-ordering principle for natural numbers. (Note that this is not the same thing as the well-ordering principle, which is equivalent to the axiom of choice and has nothing to do with induction.)