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 A

_{n}for all positive integers n (e.g., A

_{n}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:

- First, you prove that A
_{1}holds, i.e., the property holds when n = 1 (often called the base case). - Next, for every r ≥ 1 you show that if A
_{r}holds then A_{r+1}also holds (this is often called the inductive step).

_{n}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 A

_{n}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 A

_{r}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 A

_{n}holds for all n. In particular, for any a and b, if max(a, b) = r, then A

_{r}holds and hence for any a and b, a = b!

Can you see the hole in this proof?

## 2 comments:

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!

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.

Post a Comment