Induction

In mathematics, induction is a technique for proving certain types of mathematical statements. The induction principle can be illustrated by arranging a series of dominoes in a line. Suppose two facts are known about this line of dominoes.

The first domino is knocked over.
If one domino is knocked over, then the next domino is always knocked over.

What can be concluded from these statements? If the first domino is knocked over, then the second domino is knocked over, which knocks over the third, fourth, fifth, and so on, until eventually all of the dominoes fall.

Induction is a simple but powerful idea when applied to mathematical statements about positive integers. For example, consider the following statement: n² ≥ n for all positive integers, n. To prove that this statement is true using induction, it is necessary to prove two parts: first, that the statement is true for n = 1; and second, that if the statement is true for a positive integer n = k, then it must be true for n = k + 1. Demonstrating both of these parts proves that the mathematical statement has to be true for all positive integers.

Suppose using the induction principle it has been shown that n² ≥ n. It is then instructive to see how the statement is true for all positive integers, n. The first part says that n² ≥ n is true for n = 1, which is, in effect, knocking over the first domino. According to the second part, n² ≥ n is also true for n = k + 1 when it is true for n = k, so it is true for 1 + 1 = 2. This proves that the next domino is always knocked over. Now apply the second part again and take k = 2. Continuing this process proves that n² ≥ n is true for all positive integers.

Using the induction principle, it can also be shown that 2n is always an even number for all positive integers, n. Substitute 1, 2, 3, and 4 for n, and the results are 2, 4, 6, and 8, which are all even numbers. But how can it be certain that, without fail, every positive integer n will result in an even number for 2n? It looks obvious, but often what looks obvious is not necessarily a valid proof. The induction principle, however, provides a valid proof.

The mathematical statement we want to prove is that 2n is an even number when n is a positive integer. To test the first part, we know that for n = 1, 2n is 2 × 1, or 2. The first even number is 2. So the statement is true for n = 1. To test the second part, suppose that 2n is an even number for some positive integer n = k. Therefore, 2k is even. Remember, adding 2 to any even number always produces an even number. So 2k + 2 is also an even number, but 2k + 2 = 2(k + 1). Hence, 2(k + 1) is an even number. Assuming that the statement is true for n = k leads to the fact that the statement is true for n = k + 1. Therefore, the induction principle proves that 2n is an even number for all positive integers, n.

Induction

Bibliography