# principle of finite induction

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 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 already entails $P(0)$ since the statement $\forall m<0P(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. 1.

$0$ belongs to $S$, and

2. 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.)

 Title principle of finite induction Canonical name PrincipleOfFiniteInduction Date of creation 2013-03-22 11:46:41 Last modified on 2013-03-22 11:46:41 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 24 Author CWoo (3771) Entry type Theorem  Classification msc 03E25 Classification msc 00-02 Related topic TransfiniteInduction Related topic AnExampleOfMathematicalInduction Related topic Induction Related topic WellFoundedInduction Defines induction hypothesis Defines inductive hypothesis Defines base case Defines base step