Mathematical induction is a method for proving that a given predicate is true for every natural number , greater than or equal to some minimum value, usually or . This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true.

A proof by induction consists of two cases. The first called the base case, proves the predicate for some natural , usually or . The second called the induction step then proves that if the predicate holds for , where is an arbitrary natural number then it must also hold for .

The two steps in the proof (the base case and the induction step) establish that the predicate holds for for all natural numbers greater than or equal to the base case proving where is the base case chosen earlier.

Example

Statement to Prove

For all natural numbers such that

Base Case

Let . The left-hand side of the formula is:

Since both sides are equal the base case holds.

Inductive Step

Assume that the formula holds for some arbitrary natural number , i.e., assume:

This is called the inductive hypothesis.

We need to prove that the formula also holds for , i.e.,

Starting on the right-hand side for and simplifying we get

Expanding on the right side we get

Now working on the left side we can remove from the summation as follows:

Using our inductive hypothesis we can substitute for giving us:

Combining terms over a common denominator:

Expanding and combining like terms we get

As both sides are now equivalent the hypothesis can be concluded for and therefore for all naturals greater than or equal to .