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.

1. The first domino is knocked over.
2. 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.

see also Proof.

Rafiq Ladhani

Bibliography

Amdahl, Kenn, and Jim Loats. Algebra Unplugged. Broomfield, CO: Clearwater Publishing Co., 1995.

Miller, Charles D., Vern E. Heeren, and E. John Hornsby, Jr. Mathematical Ideas, 9th ed. Boston: Addison-Wesley, 2001.

induction
1. A method of logical inference in which a general but not necessarily true conclusion is drawn from a set of particular instances. In machine learning, for example, the term induction is used to describe an approach to machine learning in which generalized structures or statements are inferred from particular examples.

2. A process for proving mathematical statements involving members of an ordered set (possibly infinite). There are various formulations of the principle of induction. For example, by the principle of finite induction, to prove a statement P(i) is true for all integers i ≥ i₀, it suffices to prove that

(a) P(i₀) is true;

(b) for all k ≥ i₀, the assumption that P(k) is true (the induction hypothesis) implies the truth of P(k+1).

(a) is called the basis of the proof, (b) is the induction step.

Generalizations are possible. Other forms of induction permit the induction step to assume the truth of P(k) and also that of P(k–1), P(k–2), …, P(k–i)

for suitable i. Statements of several variables can also be considered. See also structural induction.