## You are here

Homeprinciple of finite induction

## Primary tabs

# 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<nP(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<nP(m))\Rightarrow P(n)$ 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. $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.)

## Mathematics Subject Classification

03E25*no label found*00-02

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

## Corrections

induction hypothesis by Wkbj79 ✓

typo by mps ✓

defines list by Wkbj79 ✓

typo, base step by Wkbj79 ✓