An Introduction to Mathematical Reasoning Numbers, Sets and Functions

In this chapter we discuss a special proof technique which is particularly useful when proving statements about the positive integers.

Proof by induction

Suppose that we wish to prove that some property holds for all the positive integers 1, 2, 3, 4, …. It is often difficult, or even impossible, to prove such statements simply from basic rules of arithmetic. What these rules fail to capture is the fact that the positive integers come in a sequence with any number obtainable by starting from the number 1 and adding 1 to it enough times. The integer n + 1 is called the successor of the integer n. Thus, if we start with the integer 1 and form its successor, and then its successor, and so on, then given any positive integer eventually it will be reached. This idea can be formulated more precisely as follows.

Axiom 5.1.1 (The induction principle)Suppose, that P(n) is a statement involving a general positive integer n. Then P(n) is true for all positive integers 1, 2, 3, … if

1. (i) P(1) is true, and

2. (ii) P(k) ⇒ P(k + 1) for all positive integers k.

Before discussing the induction principle further, here is an example of how it is used.

Proposition 5.1.2For all positive integers n we have the inequality n ≤ 2n.