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:
- First, you prove that A1 holds, i.e., the property holds when n = 1 (often called the base case).
- Next, for every r ≥ 1 you show that if Ar holds then Ar+1 also holds (this is often called the inductive step).
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?
