Mathematical induction

Mathematical induction is a proof method typically used to prove that a given statement is true for all natural numbers. It can also be used in more general settings as will be described below.

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.

Example:

Suppose we wish to prove the statement that the sum of the first n natural numbers, that is 1 + 2 + 3 + ... + n,
is equal to n(n + 1) / 2. The proof that the statement is true for all natural numbers proceeds as follows:

• (1) Check it is true when n = 0. Clearly, the sum of the first 0 natural numbers is 0, and 0(0 + 1) / 2 = 0. So the statement is true when n = 0.
• (2) We have to show that if the statement holds when n = m, then it holds when n = m + 1. This can be done as follows.
  • Assume the statement is true for n = m holds, i.e.,

                                m(m + 1)
              1 + 2 + ... + m = --------
                                   2

• Adding m + 1 to both sides gives

                                          m(m + 1)
              1 + 2 + ... + m + (m + 1) = -------- + (m + 1)
                                             2

• By algebraic manipulation we have

                    m(m + 1)   2(m + 1)   (m + 2)(m + 1)
                 =  -------- + -------- = --------------
                       2          2              2

• Thus we have

                                      ((m + 1))((m + 1) + 1)
              1 + 2 + ... + (m + 1) = ----------------------
                                                2

• So the statement is true for n = m + 1.
• (3) By induction we conclude that the statement holds for all natural numbers n.

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.

Another generalization allows that in the second step we not only assume that the statement holds for n = m but also for all 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 socalled 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 for this generalization it holds that it is in fact 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 with proving the statement ' P(m) for all m <= n ' for all natural numbers n with the first two steps.

The last two steps can be reformulated as one step:

1. Showing that if the statement holds for all n < m then the same statement also holds for n = m.

This is in fact the most general form of mathematical induction and it can be shown that it is not only valid for statements about natural numbers, but for statements about elements of any well-founded set, that is, a set with a partial order that contains no infinite descending chains (where < is defined such that a < b iff a <= b and a ≠ b).

This form of induction, when applied to ordinals (which form a well-ordered and hence well-founded class), is called transfinite induction. It is an important proof technique in set theory, topology and other fields.

Proofs by transfinite induction typically need to distinguish three cases:

1. m is a minimal element, i.e. there is no element smaller than m
2. m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element
3. m has no direct predecessor, i.e. m is a so-called limit-ordinal

/Talk