The induction principle
The essence of the natural number concept is … closure under the successor operation.†
Richard Dedekind (1888)
In this chapter we discuss a special proof technique which is particularly useful when proving statements about the positive integers.
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 ...