## Part 2

### New Skills

Formulating Maths
Introduction
Hypotheses &c
Implications
And & or
For all & there exists
Dependence

Proof
Introduction
Counter examples
Constructing proofs
Understanding
Experimentation
Precision
Examples
Assumptions
Induction
The End

Site map

Summary
1.
To prove that a statement P(n) is true for all positive integers n, it may be appropriate to prove the statement by induction.
2.
Proofs by induction may be by simple induction, or compound induction, or may be formulated as interative arguments or as the minimal criminal method.
3.
When you intend to prove a statement by induction, you should say so clearly, and you should make it very clear what statement is being proved.

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:

(*):
For all integers n ³ 1, P(n) holds.
Examples include the following:

Example 1. For n ³ 1,

 n å r = 1 r = n(n+1) 2 .

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:

Let n ³ 1. Then Ön is either an integer or is irrational.

Simple induction

One way to prove (*) is as follows:

(i)
Show that P(1) is true;
(ii)
Show that if P(n) is true, then P(n+1) is true.
It is easy to see that this is adequate to prove that P(n) is true for all n. Firstly, (i) ensures that P(1) is true; then, (ii) with n = 1 ensures that P(2) is true; then, (ii) with n = 2 ensures that P(3) is true, etc. Thus, if someone were to specify a positive integer (say, 319), you could tell them that P(319) is true, by (i) and 318 applications of (ii). In other words, P(n) is true for all n = 1,2,.... Note, however, that this method does not tell you that P(¥) is true, even if the statement P(n) makes sense, when n is replaced by ¥; the fact that P(n) is true for all finite (but arbitrary) n does not imply that P(¥) is true.

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:

 P(n): n å r = 1 r = n(n+1) 2 .
Firstly, P(1) holds, since for n = 1 both the left and right hand sides equal 1.

Now, suppose that P(n) holds for some n ³ 1. Then

 n+1 å r = 1 r = n å r = 1 r + (n+1) = n(n+1) 2 + n+1 = (n+1)(n+2) 2 ,
so P(n+1) holds.

It follows, by induction, that P(n) holds for all n ³ 1.

Example 2. We shall prove the following by induction on n:

 P(n): ó õ 2p 0 (cosq)2n dq = (2n)!p 22n-1(n!)2 .

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

 ó õ 2p 0 (cosq)2(n+1) dq
 = ó õ 2p 0 (cosq)2n+1cosq dq
 = [(cosq)2n+1sinq)]0 2p - ó õ 2p 0 (2n+1)(cosq)2n(-sinq)sinq dq
 = (2n+1) ó õ 2p 0 (cosq)2n(sinq)2 dq
 = (2n+1) ó õ 2p 0 ((cosq)2n -(cosq)2(n+1))  dq,
where we used integration by parts in the second line and the formula (cosq)2 + (sinq)2 = 1 in the fourth line. Hence,
 ó õ 2p 0 (cosq)2(n+1) dq = 2n+1 2n+2 ó õ 2p 0 (cosq)2n dq = 2n+1 2n+2 (2n)!p 22n-1(n!)2 = (2n+2)!p 22n+1((n+1)!)2 ,
where we used P(n) in the second equality. Thus P(n+1) is true.

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.

Compound induction

Another way to prove that P(n) is true for all positive integers n is as follows:

(i)
Show that P(1) is true;
(ii)
Show that if P(n) is true for all n = 1,2,...,k, then P(k+1) is true.
Again, it should be clear that this is adequate to prove that P(n) is true for all integers n. A proof of this type is said to be a proof by (compound) induction; in this case, the inductive hypothesis is:
Suppose that P(n) is true for all n = 1,2,...,k.
Indeed, a proof of P(n) by compound induction is essentially the same as a proof of P(k)* by simple induction, where:
P(k)*:
P(n) is true for all n = 1,2,...,k.
Example 4. We shall prove, by induction on n, that every integer n ³ 2 is a product of primes.

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,

 ak+1
 = ak + 2ak-1 - 2(k-1) + 1
 = 2k + k + 2(2k-1+k-1) - 2k + 3
 = 2k + 2k + k + 1
 = 2k+1 + (k+1).
This completes the inductive step. Hence, by induction, an = 2n + n for all n ³ 1.

Iterative arguments

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 = ó õ 2p 0 (cosq)n dq       (n ³ 0).
Then
 In
 = ó õ 2p 0 (cosq)2n-1cosq dq
 = [(cosq)2n-1sinq)]0 2p - ó õ 2p 0 (2n-1)(cosq)2n-2(-sinq)sinq dq
 = (2n-1) ó õ 2p 0 (cosq)2n-2(sinq)2 dq
 = (2n-1) ó õ 2p 0 ((cosq)2(n-1) -(cosq)2n)  dq,
where we used integration by parts in the second line and the formula (cosq)2 + (sinq)2 = 1 in the fourth line. Hence,
 2nIn = (2n-1) In-1,
and, by iteration,
 In = 2n-1 2n In-1 = (2n-1)(2n-3) 2n(2n-2) In-2 . . . . . . . . . . = (2n-1)(2n-3)...1 2n(2n-2)...2 I0.
But I0 = ò02p dq = 2 p, so
 In = 2n(2n-1)(2n-2)(2n-3)...2.1 2n(2n)(2n-2)(2n-2)...2.2 2p = (2n)!p 22n-1(n!)2 .

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.

Minimal criminals

There is one more variant of induction which is worth mentioning here. Another way to prove (*) is the following:

Assume that there is a smallest integer k such that P(k) is false, and deduce a contradiction (e.g., by showing that there is an integer n < k such that P(n) is false).
This argument is valid because if there were a positive integer n such that P(n) is false, then there would be a smallest positive integer k such that P(k) is false. If we call an integer n criminal if P(n) is false, then k is a minimal criminal, so such a proof is sometimes known as a minimal criminal argument. Essentially, a least criminal argument is what you get by combining the concept of proof by induction with the concept of proof by contradiction ( Contradiction). An example of a least criminal argument follows.

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,
December 1999.
 previous main page top next