Sunday, April 20, 2008

What is Mathematics: Mathematical Induction

This is the first in my series on some interesting and important techniques and results described in the book What is Mathematics. The first chapter introduces the natural numbers, 1, 2, 3, ... In Leopold Kronecker's words: "God created the natural numbers; everything else is man's handiwork."

After introducing the basics of natural numbers, the authors introduce the fundamental technique of the principle of mathematical induction. This is a very simple, yet powerful, method for proving theorems about an infinite sequence of cases. In its simplest form, suppose you want to prove that a property An for all positive integers n (e.g., An might be the proposition that (1 + p)n ≥ (1 + np) for any p > -1). The principle of mathematical induction states that you can prove this using two steps:
  1. First, you prove that A1 holds, i.e., the property holds when n = 1 (often called the base case).
  2. Next, for every r ≥ 1 you show that if Ar holds then Ar+1 also holds (this is often called the inductive step).
One can see that the above two steps serve to establish An for all n ≥ 1.
The proposition that (1 + p)n ≥ (1 + np) for any p > -1 can be easily established using mathematical induction (this will prove to be a useful little inequality).

The principle of mathematical induction needs to be applied with care. The authors demonstrate the pitfalls of this method with the following "proof" that all numbers are, in fact, equal!

Let An be the statement "If a and b are any two positive integers such that max(a, b) = n, then a = b". The base case is certainly true: when n = 1, a and b must both be 1 (being positive integers). For the inductive case, assume Ar holds and let a and b be such that max(a, b) = r + 1. Clearly, then max(a - 1, b - 1) = r, and hence by assumption a - 1 = b - 1. Hence a = b. So An holds for all n. In particular, for any a and b, if max(a, b) = r, then Ar holds and hence for any a and b, a = b!

Can you see the hole in this proof?


Shashi said...

This post is crying out for a comment..

Well, the statement max(a-1,b-1)=n-1 is not true for all possible values of a and b. Specifically, for n=2, it is not true when a=1, as a-1=0, for which there is no claim in A_1. Since a, b are positive numbers, and max(a,b)=2, then a=b=2 is the only case where the statement is true, and hence the only case when A_2 can be inferred.

To reuse the "proof", you could restate the "theorem" to: if a=b=n and max(a,b)=n then a=b. While true, it is not a very useful proposition!

Now, what is wrong with the following "proof" of the "theorem" A_n: Any set with n elements has all equal elements. I remember this from college days, and it had me baffled for some time at that time.

Base case A_1 - Clearly true for all sets with one element.

Induction assumption is A_(n-1). Let S_n be a set with n members. Take any two distinct elements a, b from S_n. We will prove them to be equal as follows: By the truth of A_(n-1), S_n-{a} has all equal members and so does S_n-{b}. Now let c be an element of S_n-{a,b}. Since, c, b are in S_n-{a}, c=b. Similarly, since c,a are in S_n-{b}, c=a. Hence, a=b=c and so a=b. Since a and b are arbitrary members of S_n, A_n holds. QED!

Pandu Nayak said...

Your "proof" also fails in the same way. S_2 has only two elements, say {a, b}. In this case, there's no c that satisfies the conditions needed for the proof, and the inductive step fails.

/* Google Analytics tracking */