We have seen one example of a proof by induction in the solution of our earlier Example 5. Here, we want to explain the method in more detail. (Induction is also discussed in Alice In Numberland, Chapter 5, and in various other books.)
Induction is useful when it is required to prove a statement where the conclusion is, or can be formulated as:
Example 1. For n ³ 1,
Example 2. For n ³ 1, ò02p (cosq)2n dq = [((2n)!p)/(22n-1(n!)2)].
Example 3. Let f : Q ® R be a function such that f(x+y) = f(x)+f(y) for all x and y in Q. Then f(nx) = nf(x) for all x Î Q and all n ³ 1.
Example 4. Let n be an integer with n ³ 2. Then n is a product of (one or more) primes.
Example 5. Suppose that (an)n ³ 1 is a sequence of real numbers such that a1 = 3, a2 = 6, and an+2 = an+1 + 2an -2n +1 for all n ³ 1. Then an = 2n +n for all n ³ 1.
Example 6. Suppose that n is an integer which is not a perfect square. Then Ön is irrational.
The statement in Example 4 is a well-known fact, and the reader may not previously have thought of it as needing proof.
In some cases such as Example 6, it is not immediately apparent that we are asked to prove a conclusion of the form (*), until the problem is reformulated. Indeed, Example 6 is equivalent to:
One way to prove (*) is as follows:
A proof by this method is known as a proof by (simple) induction, and P(n) is the inductive statement to be proved. Stage (i) of the proof is known as the base case, and stage (ii) as the inductive step. At the beginning of the inductive step, one makes the inductive hypothesis: Suppose that P(n) holds for some n.
You should note that in (*), n is a dummy variable, which can be replaced by another variable, i.e. proving that P(n) is true for all n is the same as proving that P(k) is true for all k. When you are presenting a proof by induction, you should make a clear statement of the inductive hypothesis P(n), and you should make clear the name of the dummy variable.
Let us see how this method works in some of our examples.
Example 1. We shall prove the following by induction on n:
Now, suppose that P(n) holds for some n ³ 1. Then
It follows, by induction, that P(n) holds for all n ³ 1.
Example 2. We shall prove the following by induction on n:
For n = 0, the left-hand side of the equation P(0) is: ò02p dq = 2p, and the right-hand side is: p/(2-1) = 2p. Thus, P(0) holds.
Now, suppose that P(n) holds for some n ³ 0. Then
It follows by induction that P(n) is true for all n ³ 1.
For a formal proof of Example 3 by induction, you are referred to the solution of the earlier Example 5.
Another way to prove that P(n) is true for all positive integers n is as follows:
For n = 2, this is trivial, since 2 is itself prime.
Now, let k ³ 2. We assume as inductive hypothesis that every integer n such that 2 £ n £ k is a product of primes. Now, there are two cases:
Case 1: k+1 is prime. Then k+1 is the product of one prime, itself.
Case 2: k+1 is not prime. Then k+1 = mn for some m,n ³ 2. Then m,n £ k. By the inductive hypothesis, m and n are both products of primes, say m = p1p2... pr, n = q1q2 ...qs+1. Then k+1 = p1p2 ... prq1q2 ... qs, which is a product of primes.
In each case, we have shown that k+1 is a product of primes. This completes the inductive step. It follows, by induction, that every integer n ³ 2 is a product of primes.
Example 5. We shall prove that an = 2n + n for n ³ 1, by induction on n. For n = 1 and n = 2, this is trivial since we are given that a1 = 3 and a2 = 6.
Now suppose that an = 2n + n for all n = 1,2,...,k, for some k ³ 2. Then, in particular, ak-1 = 2k-1 + (k-1) and ak = 2k+ k. Now taking n = k-1 in the given recurrence relation,
We have already explained that a proof by induction works because the inductive step (ii) may be applied iteratively as many times as is needed. For this reason, it is not surprising that some proofs which might be given by induction (and perhaps should be given by induction, if one is being extremely fussy) can be set up as arguments by iteration. An example of this is the proof of Example 2 above, which we now set out in a slightly less formal way.
Example 2. Let
In many examples, the iterative argument is so simple that it would be futile to formulate it as a proof by induction (see the iteration near the end of the solution of the earlier Example 6). In some examples such as Example 2 here, there is not much to choose between the two methods. In other examples where a proof by induction can be given, it is not feasible to set this out as an iterative argument, e.g., Examples 1 and 5 in this section. There is no hard-and-fast rule which tells you when an iterative argument is possible and when it is not. However, the process of experimentation (Experimentation) which led you towards a proof by induction or iterative argument, and your attempts to give a rigorous argument (Precision), should also indicate whether you need to give a formal proof by induction.
There is one more variant of induction which is worth mentioning here. Another way to prove (*) is the following:
Example 6. Suppose that there is a positive integer n such that Ön is neither an integer nor irrational. Then there is a least such integer k. Now, Ök must be rational, but not an integer, so Ök = m/n, where m and n are positive integers and n ³ 2. We may assume that m and n have no common factor. Let p be a prime dividing k. Then p divides n2k. But n2k = m2, so p divides m2. Since p is prime, it follows that p divides m. Hence p2 divides n2k. Since m and n are coprime, p2 must divide k. Thus k = p2a and m = pb for some positive integers a and b. Now Öa = b/n, which is neither an integer nor irrational. But a < k. This contradicts the choice of k as the least such integer. It follows that, for all n ³ 1, Ön is either an integer or is irrational.
Note that this minimal criminal argument is not the only solution of Example 6. In principle, it is always possible to reorganise a minimal criminal argument as induction (try doing this for Example 6), but there are some cases where minimal criminals are the best approach. A striking example is the successful (1976) proof of the Four Colour Theorem (see Counter examples).
| Design: Paul Gartside,
Content: Prof. C. Batty,