O'Reilly logo

An Introduction to Mathematical Reasoning by Peter J. Eccles

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5

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.

5.1 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required