Home > Mathematical induction

The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:

1. Showing that the statement holds when n = 0.
2. Showing that if the statement holds for n = m, then the same statement also holds for n = m + 1.

To understand why the two steps are in fact sufficient, it is helpful to think of the domino effect: if you have a long row of dominos standing on end and you can be sure that

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.

then you can conclude that all dominos will fall.

1 Example

Suppose we wish to prove the statement:

for all natural numbers n. This is a simple formula for the sum of the natural numbers up to the number n. The proof that the statement is true for all natural numbers n proceeds as follows.

1.1 Proof

Check if it is true for n = 0. Clearly, the sum of the first 0 natural numbers is 0, and 0(0 + 1) / 2 = 0. So the statement is true for n = 0. We could define the statement as P(n), and thus we have that P(0) holds.

Now we have to show that if the statement holds when n = m, then it also holds when n = m + 1. This can be done as follows.

Assume the statement is true for n = m, i.e.,

Adding m + 1 to both sides gives

By algebraic manipulation we have

Thus we have

This is the statement for n = m + 1. Note that it has not been proven as true: we made the assumption that P(m) is true, and from that assumption we derived P(m + 1). Symbolically, we have shown that:

However, by induction, we may now conclude that the statement P(n) holds for all natural numbers n:

1. We have P(0), and thus P(1) follows
2. With P(1), P(2) follows
3. ... etc

2 Generalizations

2.1 Start at b

This type of proof can be generalized in several ways. For instance, if we want to prove a statement not for all natural numbers but only for all numbers greater than or equal to a certain number b then the following steps are sufficient:

1. Showing that the statement holds when n = b.
2. Showing that if the statement holds for n = m then the same statement also holds for n = m + 1.

This can be used, for example, to show that n² > 2n for n ≥ 3. Note that this form of mathematical induction is actually a special case of the previous form because if the statement that we intend to prove is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with the first two steps.

2.2 Assume true for all lesser values

Another generalization, called complete induction, allows that in the second step we assume not only that the statement holds for n = m but also that it is true for n smaller than or equal to m. This leads to the following two steps:

1. Showing that the statement holds when n = 0.
2. Showing that if the statement holds for all n ≤ m then the same statement also holds for n = m + 1.

This can be used, for example, to show that

fib(n) = [Φⁿ − (−1/Φ)ⁿ ] / 5^1/2

where fib(n) is the n^th Fibonacci number and Φ = (1 + 5^1/2) / 2 (the so-called golden mean). Since fib(m + 1) = fib(m) + fib(m − 1) it is straightforward to prove that the statement holds for m + 1 if we can assume that it already holds for both m and m − 1.

Also this generalization is just a special case of the first form:

let P(n) be the statement that we intend to prove,

then proving it with these rules is equivalent to proving

the statement ' P(m) for all m ≤ n ' for all natural numbers n with the first two steps.