- Shopping Bag ( 0 items )
So, naturalists observe, a flea Hath smaller fleas that on him prey; And these have smaller still to bite 'em; And so proceed ad infinitum.
There are many styles of proof, and mathematical induction is one of them. We begin by saying what mathematical induction is not. In the natural sciences, inductive reasoning is based on the principle that a frequently observed phenomenon will always occur. Thus, one says that the sun will rise tomorrow morning because, from the dawn of time, the sun has risen every morning. This is not a legitimate kind of proof in mathematics, for even though a phenomenon occurs frequently, it may not occur always.
Inductive reasoning is valuable in mathematics, because seeing patterns often helps in guessing what may be true. On the other hand, inductive reasoning is not adequate for proving theorems. Before we see examples, let us make sure we agree on the meaning of some standard terms.
Definition. An integer is one of 0, 1, – 1, 2, – 2, 3, – 3, ...
Definition. An integer p ≥ 2 is called a prime number if its only positive divisors are 1 and p. An integer m ≥ 2 which is not prime is called composite.
A positive integer m is composite if it has a factorization m = ab, where a< m and b < m are positive integers; the inequalities are present to eliminate the uninteresting factorization m = m x 1. Notice that a = 2: since a is a positive integer, the only other option is a = 1, which implies b = m (contradicting b< m); similarly, b ≥ 2.
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. That this sequence never ends is proved in Exercise 2.10.
Consider the statement:
f (n) = n2 - n + 41 is a prime number for every n = 1
(this is really a whole family of statements, one for each positive integer n). As we evaluate f (n) for n = 1, 2, 3, 4, ..., 40, we obtain the following values:
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.
It is tedious but not difficult (see Exercise 1.7) to prove that every one of these numbers is prime. Can we now conclude that all the numbers of the form f (n) are prime? For example, is the next number f (41) = 1681 prime? The answer is no: f (41) = 412 - 41 + 41 = 412, which obviously factors, and hence f (41) is not prime.
Here is a more spectacular example (which I first saw in an article by W. Sierpinski). A perfect square is an integer of the form a2 for some positive integer a; the first few perfect squares are: 1, 4, 9, 16, 25, 36, 49. Consider the statements S(n), one for each n ≥ 1:
S(n): 991n2 + 1 is not a perfect square.
It turns out that many of the statements S(n) are true. In fact, the smallest number n for which S(n) is false is
n = 12, 055, 735, 790, 331, 359, 447, 442, 538, 767 [approximately equals to] 1.2 × 1028.
The original problem is a special case of Pell's equation (given a prime p, when are there integers m and n with m2 = pn2 + 1), and there is a way of calculating all possible solutions of it. In fact, an even more spectacular example of Pell's equation involves the prime p = 1, 000, 099; the smallest n for which 1, 000, 099n2 + 1 is a perfect square has 1116 digits.) The latest scientific estimate of the age of the earth is 20 billion (20,000,000,000) years, or about 7.3 × 1012 days, a number very much smaller than 1.2 × 1028, let alone 101115. If, starting on the very first day, mankind had verified statement S(n) on the nth day, then there would be, today, as much evidence of the general truth of these statements as there is that the sun will rise tomorrow morning. And yet some statements S(n) are false!
As a final example, let us consider the following statement, known as Goldbach's Conjecture: Every even number m ≥ 4 is a sum of two primes. For example,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
It would be foolish to demand that all odd numbers be sums of two primes. For example, suppose that 27 = p + q, where p and q are primes. If both p and q are odd, then their sum is even, contradicting 27 being odd. Since the only even prime is 2, we have 27 = 2 + q, and so q = 25 is prime; this contradiction shows that 27 is not a sum of two primes.
No one has ever found a counterexample to Goldbach's conjecture, but neither has anyone ever proved it. At present, the conjecture has been verified for all even numbers m ≤ 1013 by H. J. J. te Riele and J.-M. Deshouillers. It has been proved by J.-R. Chen (with a simplification by P. M. Ross) that every sufficiently large even number m can be written as p + q, where p is prime and q is "almost" a prime; that is, q is either prime or a product of two primes. Even with all this positive evidence, however, no mathematician will say that Goldbach's conjecture must, therefore, be true for all even m.
We have seen what mathematical induction is not; let us now discuss what induction is. Suppose one guesses that all the statements S(n) of a certain sort are true (for example, suppose that S(n) has been observed to be true for many values of n). Induction is a technique of proving that all the statements S(n) are, indeed, true. For example, the reader may check that 2n> n for many values of n, but is this inequality true for every value of n? We will prove below, using induction, that this is so.
The key idea is just this. Imagine a stairway to the sky; if its first step is white, and if the next step above a white step is also white, then all the steps of the stairway must be white. One can trace this idea back to Levi ben Gershon in 1321. There is an explicit description of induction (cited by Pascal) written by Francesco Maurolico in 1557.
Our discussion is based on the following property of positive integers (usually called the Well Ordering Principle).
Least Integer Axiom. Every nonempty collection C of positive integers has a smallest number in it.
Saying that C is nonempty merely means that there is at least one integer in the collection C.
The Least Integer Axiom is certainly plausible. Given a nonempty collection C, check whether 1 is a number in C; if it is, then 1 is the smallest number in C. Otherwise, check whether 2 is a number in C; if it is, then 2 is the smallest number in C; if not, check whether 3 is a number in C. Continue this procedure; since there is some number in C, we will eventually bump into it.
The Least Integer Axiom can be restated in a more useful way.
Theorem 1.1 (Least Criminal). Let S(n) be a family of statements, where n varies over some nonempty collection of positive integers. If some of these statements are false, then there is a first false statement.
Proof. Let C be the collection of all those positive integers n for which S(n) is false; by hypothesis, C is nonempty. The Least Integer Axiom provides a smallest number m in C, and S(m) is the first false statement.
Theorem 1.2. Every integer n ≥ 2 is either a prime or a product of primes.
Proof. Were this not so, there would be a "least criminal" m; that is, m ≥ 2, m is neither a prime nor a product of primes, and m is the smallest such integer. Since m is not a prime, it is composite: there is a factorization m = ab with a < m and b< m. Because m is the least criminal, both a and b are "honest"; i.e., a = pp'p "for primes p, p', p", ..., and b = qq'q" ... for primesq, q', q",.... Therefore, m = pp' p" ... qq'q" ... is a product of (at least two) primes, a contradiction.
Mathematical induction is a version of Least Criminal that is usually more convenient to use.
Theorem 1.3 (Mathematical Induction). Let S(n) be a family of statements, one for each n ≥ 1, and suppose that:
(i) S(1) is true, and
(ii) if S(n) is true, then S(n + 1) is true.
Then S(n) is true for every n = 1.
Proof. It suffices to show that there are no integers n for which S(n) is false; that is, it suffices to show that the collection
C = all positive integers n for which S (n) is false
If, on the contrary, C is nonempty, then there is a first false statement, say,S(m). Since S(1) is true, by (i), we must have m ≥ 2. This implies that m - 1 ≥ 1, and so there is an (m - 1)st statement S(m - 1) [there is no statement S(0)]. As m is the least criminal, m - 1 must be honest; that is, S(m - 1) is true. But (ii) says that S(m) = S([m - 1] + 1) is also true, and this is a contradiction. We conclude that C is empty and, hence, that all the statements are true.
Before we illustrate how to use mathematical induction, let us make sure we can manipulate inequalities. We recall that if two real numbers a and b are both positive, i.e., a > 0 and b > 0, then ab,a + b and 1/a are also positive. On the other hand, the product of a positive number and a negative number is negative.
Definition. For any two real numbers c and d, define
d < c
to mean that c - d is positive. We write d ≤ c to mean either d< c or d = c.
Notice that if a >b and b > c, then a >c [for a - c = (a - b) + (b - c) is a sum of positive numbers and, hence, is itself positive]. One often abbreviates these two inequalities as a > b > c. The reader may check that if a >b ≥ c, then a >c.
Theorem 1.4. Assume that b< B are real numbers.
(i) If m is positive, then mb< mB, whereas if m is negative, then mb >mB.
(ii) For any number N, positive, negative, or zero, we have
N + b < N + B and N - b > N - B.
(iii) Let c and d be positive numbers. If d< c, then 1/d > 1/c, and, conversely, if 1/c< 1/d, then c > d.
Proof. (i) By hypothesis, B - b > 0. If m > 0, then the product of positive numbers being positive implies that m(B - b) = mB - mb is positive; that is, mb< mB. If m < 0, then the product m(B - b) = mB - mb is negative; that is,mB< mb.
(ii) The difference (N + B) - (N + b) is positive, for it equals B - b. For the other inequality, (N - b) - (N - B) = - b + B is positive, and, hence, N - b > N - B.
(iii) If d< c, then c - d is positive. Hence, 1/d -1/c = (c - d)/cd is positive, being the product of the positive numbers c - d and 1/cd (by hypothesis, both c and d are positive). Therefore, 1/d > 1/c. Conversely, if 1/c< 1/d, then part (i) gives d = cd (1/c) < cd (1/d) = c; that is, c >d.
To illustrate, since 3 < 4, we have
9 x 3 = 27 < 36 = 9 x 4; (i)
(-9) x 3 = -27 > -36 = (-9) x 4; 9 + 3 = 12 < 13 9 + 4; 9 - 3 = 6 > 5 = 9 - 4; (ii)
1/4 = 0.25 <0.33 < 1/3. (iii)
It is always a good idea to see concrete examples of a theorem, for it makes the result more understandable by putting flesh on the bones of the statement. This is the first step in appreciating what a theorem means, and so it is an important habit to cultivate. Indeed, mathematics must be read with pencil and paper. If no example is given in a text, supply your own. There is an apocryphal story of a theorem so general that no particular case is known. Such a theorem would be bad mathematics.
Theorem 1.5. 2n >n for all n ≥ 1.
Proof. Regard this inequality as a sequence of statements, where the nth statement S(n) is:
S(n): 2n >n.
There are two steps required for mathematical induction.
Base step: The initial statement
S(1) : 21 > 1
is true, for 21 = 2 > 1.
Inductive step: If S(n) is true, then S(n + 1) is also true; that is, if one uses the inductive hypothesis S(n) : "2n >n is a valid inequality," then one can prove
S(n +1): 2n +1 >n + 1.
First, multiply both sides of 2n >n by 2; Theorem 1.4(i) gives
2n +1 = 2 × 2n > 2n.
Now 2n = n + n ≥ n + 1 (because n ≥ 1); therefore, 2n +1 > 2n ≥ n + 1, and so 2n +1 >n + 1, as desired.
Having verified both the base step and the inductive step, we conclude that 2n >n for all n ≥ 1.
Induction is plausible in the same sense that the Least Integer Axiom is plausible. Suppose that statements S(1), S (2), S(3), ? satisfy the hypotheses of mathematical induction. Since S(1) is true, so is S(2); since S(2) is true, so is S(3); since S(3) is true, so is S(4); and so forth. Induction replaces the phrase and so forth by the inductive step; this guarantees, for every n, that there is never an obstruction in the passage from a statement S(n) to the next one, S(n + 1).
Here are two comments before giving more applications of induction. First, one must verify both the base step and the inductive step; verification of only one of them is inadequate. For example, consider the statementsS(n): n2 = n. The base step S(1) is true, but one cannot prove the inductive step (of course, these statements are false for all n > 1). Another example is given by the statements S(n): n >n +1. The next statement, S(n +1), is: n +1 >n +2, and Theorem 1.4(ii) shows that the inductive step is true: if n >n + 1, then adding 1 to both sides gives n + 1 > (n + 1) + 1. But the base step is false (of course, all these statements are false).
Second, when first seeing induction, many people suspect that the inductive step is circular reasoning: one is using S(n), and this is what one wants to prove! A closer analysis shows that this is not at all what is happening. The inductive step, by itself, does not prove that S( n + 1) is true. Rather, it says that if S (n) is true, then one can prove that S(n +1) is also true. In other words, the inductive step proves that the implication "If S(n) is true, then S(n + 1) is true" is correct. The truth of this implication is not the same thing as the truth of its conclusion. For example, consider the two statements: "Your grade on every exam is 100%" and "Your grade in the course is A." The implication: "If all your exams are perfect, then you will get the highest grade in the course" is true. Unfortunately, this does not say it is inevitable that your grade in the course will be A. The truth of an implication together with the truth of its hypothesis guarantee the truth of the conclusion; the truth of only the implication does not guarantee the conclusion. Our discussion above gives a mathematical example. The implication "If n >n + 1, then n + 1 >n + 2" is correct, but the conclusion "n + 1 >n + 2" is false. (There is a discussion of implication, from the viewpoint of truth tables, given in the Glossary at the end of the book.)
This is an appropriate time to mention the converse of an implication. The converse of "If P is true, then Q is true" is the implication "If Q is true, thenP is true." It is possible that both an implication and its converse are true, in which case we say: "P is true if and only if Q is true." On the other hand, it is possible that an implication is true but that its converse is false. For example, the converse of the implication: "If all your exams are perfect, then you will receive the highest grade in the course" is "If you received the highest grade in the course, then all your exams were perfect." Fortunately, this converse is false. One need not be perfect to receive the grade A. According to my grading scheme, you receive the grade A in the course if and only if your exams average 90% or higher.
The next application of induction verifies a formula giving the sum of the first n integers.
Excerpted from Journey into Mathematics by Joseph J. Rotman. Copyright © 2007 Joseph J. Rotman. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
|To the Reader|
|To the Instructor|
|The Pythagorean Theorem||45|
|The Method of Diophantus||64|
|3||Circles and [pi]||98|
|The Area of a Disk||107|
|The Circumference of a Disk||117|
|De Moivre's Theorem||171|
|Cubics and Quartics||183|
|Glossary of Logic||217|