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?