![]()
1. The Method of Mathematical Induction
1. EXAMPLES OF UNSOUND INDUCTION IN MATHEMATICS
First let us consider two examples of the sort of induction which is inadmissible in mathematics.
EXAMPLE 1. Let
The following equalities are easy to verify:
On the basis of these four results, one might conclude that for all natural numbers n it is true that
EXAMPLE 2. Next let us consider the trinomial x2 + x + 41, first considered by the famous mathematician L. Euler.1 If we replace x by the number 0 in this trinomial, we obtain the prime number 41. If we replace x by the number 1, we again obtain a prime number, namely 43. If we continue in this manner and replace x by the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10, successively, we obtain in each case a prime number: 47, 53, 61, 71, 83, 97, 113, 131, 151, respectively. On the basis of these results one might conclude that for any nonnegative integer x, the value of the trinomial is a prime number.
Why is the reasoning used in these examples inadmissible in mathematics? In what way is the reasoning invalid?
In both the examples the reasoning employed led us to assert a general statement referring to any n (or any x) on the basis that the statements had been found true for certain particular values of n (or of x). It so happens that the general statement obtained in Example 1 is true, as we shall see below in Example 5; however, the general statement obtained in Example 2 is false. Indeed, while it can be shown that the trinomial x2 + x + 41 yields prime numbers for x = 0, 1, 2, 3, ... , 39, for x = 40 the value of the trinomial is seen to be 412, which is a composite number.
Induction has wide applications in mathematics, but it must be used with care or it may lead to erroneous conclusions.
1. MORE EXAMPLES OF UNSOUND INDUCTION
We have encountered in Example 2 a statement which proves to be true in forty instances, but which is not true in general. We shall give two additional examples of statements which are true in some particular instances without being true in general.
EXAMPLE 3. The binomial xn – 1 (where n is a natural number) is of great interest to mathematicians as it is closely related to the geometric problem of dividing a circle into n equal parts. Hence, it is not surprising that this binomial has been studied with great care, with particular attention to the question of resolving it into factors with integral coefficients.
In studying these factorizations for many particular values of n, mathematicians noted that in each of the cases studied, the absolute values of the coefficients of the factors never exceeded the number 1. Thus,
Tables of coefficients were made, and in each case the coefficients had the property mentioned above. Nevertheless, all attempts to prove the statement true for all values of n failed.
The problem was finally solved in 1941 by V. Ivanov with the following result: If n < 105, the binomial xn – 1 has the above property. One of the factors of x105 – 1, however, is the polynomial
which no longer has this property.
EXAMPLE 4. Into how many parts is space divided by n planes which pass through the same point, but no three of which intersect in the same straight line?
Let us consider the simplest special cases of this problem: One plane divides space into 2 parts. Two planes passing through a common point divide space into 4 parts. Three planes passing through a common point, but having no line in common, divide space into 8 parts.
At first glance it may appear that as the number of planes increases by 1, the number of parts into which they divide space is doubled, so that 4 planes would divide space into 16 parts, 5 planes into 32 parts, and so on; or, in general, that n planes would divide space into 2n parts.
Actually, this is not the case: 4 planes divide space into 14 parts, 5 planes into 22 parts. In general, n planes divide space into n(n – 1) + 2 parts.1
These examples illustrate the following simple but important fact: A statement may be true in many special instances and yet not be true in general.
1. THE PRINCIPLE OF MATHEMATICAL INDUCTION
Now the following question arises: Suppose that we have a statement involving natural numbers which we have found to be true in some particular instances. How can we determine whether the statement is true in general; or, to be more specific, how can we determine whether the statement is true for all natural numbers n = 1, 2, 3, ... ?
This question can sometimes be answered by using a special method of reasoning called the method of mathematical induction (complete induction), based on the following principle:
A statement is true for every natural number n if the following conditions are satisfied:
Co...
