10.4. Mathematical Induction
Mathematical induction is a very powerful technique for proving certain types of mathematical formulas. We have already used it once, in our proof of De Moivre's formula in Section 6.6. Mathematical induction, more commonly just called induction, proceeds as follows: Let P(n) be a mathematical statement, known as a proposition, which is claimed to be true for some fixed positive integer n. An example might be the following assertion:
P(n): 1 + 3 + 5 + ... + (2n - 1) = n2.
How can we prove that P(n) holds for all positive integers n? We can certainly verify it for several particular values of n, but this can never prove that it holds true for all n since there are a infinite number of cases to try. Instead, what we do is to first prove that P(n) holds for n=1. This case is known as the base case, because this is the smallest value of n for which the proposition has been formulated. It is certainly true that P(1) holds, for P(1) reduces to the obvious equality 1 = 12. A second step, known as the induction step, will complete the proof. The induction step is to first assume that P(n) holds for some arbitrary fixed positive integer n, and then to prove that it must hold for n+1 as well. (The assumption that P(n) holds is known as the induction hypothesis.) For our example, we assume P(n) and try to prove P(n+1). In other words, we are assuming that 1 + 3 + 5 + ... + (2n - 1) = n2 for some fixed n and trying to prove that 1 + 3 + 5 + ... + [2(n+1) - 1] = (n+1)2. But by our induction hypothesis, the left side is equal to n2 + [2(n+1) - 1] = n2 + 2n + 1. But we know that this is equal to (n+1)2. This proves P(n+1) and completes our proof by induction.
Why does mathematical induction work? It is easy to see that it works by thinking of it as proving a chain of propositions P(n) for n increasing in steps of 1. We started by proving P(1). To get P(2), we proved that P(n+1) follows from P(n) for all n. Thus, P(1) implies P(2). But we already proved P(1), so P(2) follows. Similarly, P(3) follows from P(2), P(4) follows from P(3), and so on.
Mathematical induction should not be confused with scientific induction. Mathematical induction is really a form of deduction, which is how all mathematical proofs work. The reason it is called induction is because it involved generalizing a proposition which we show to be true for a finite set of cases, here just the base case, and from that induce that it is true for all cases. Scientific induction is similar in that many (in fact, virtually all) scientific laws are formed by looking at a finite, though usually very large, number of base cases and inferring from this limited data that it is true for all cases. An example would be the law of falling bodies, which we stated in Section 1.10, namely that in the absense of air resistance, near the surface of the earth, all massive bodies accelerate toward the ground at 9.8 meters per second per second. The reason we believe this to be true is that it has been verified in every laboratory test anyone has ever performed. But it is still possible, though highly unlikely, that some massive bodies do not obey this law and that scientists just missed these cases.
Example 1: Prove Equation (10.2.2) by induction.
Solution: We must prove the following proposition for every positive integer n:
P(n): 1 + 2 + 3 + ... + n = n(n+1) / 2.
First we prove the base case P(1), which asserts that 1 = (1)(1+1)/2. But this is trivially true since the right side is equal to (1)(2)/2 = 2/2 = 1. This proves the base case. Now for the induction step. We first assume that P(n) holds for some fixed value of n. We must prove that P(n+1) also holds. P(n+1) is the following proposition:
P(n+1): 1 + 2 + 3 + ... + n + (n+1) = (n+1)(n+2) / 2.
By our induction hypothesis, the left side is equal n(n+1)/2 + (n+1) = (n+1)(n/2 + 1) = (n+1)(n+2) / 2, which is equal to the right side. This proves P(n+1) and completes our proof by induction.
Example 2: Prove Equation (10.3.1) by induction.
Solution: For fixed real numbers a and r≠1, we must prove the following proposition for every nonnegative integer n:
P(n): a + ar + ar2 + ar3 + ... + arn = a(rn+1 - 1) / (r - 1).
First we prove the base case P(0), which asserts that a = a(r - 1) / (r - 1), which is trivally true. (Note that in this case, the base case is for n=0, not n=1.) Now for the induction step. We first assume that P(n) holds for some fixed value of n. We must prove that P(n+1) also holds. P(n+1) is the following proposition:
P(n+1):a + ar + ar2 + ar3 + ... + arn + arn+1 = a(rn+2 - 1) / (r - 1).
By our induction hypothesis, the left side is equal to
a(rn+1 - 1) / (r - 1) + arn+1 = a[(rn+1 - 1) / (r - 1) + rn+1]
= a(rn+1 + 1 + rn+2 - rn+1) / (r - 1)
= a(rn+2 - 1) / (r - 1).
This proves the proposition P(n+1) and completes our proof by induction.