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

No credit card required

### 1.4   INDUCTION FROM A USER’S PERSPECTIVE

In this section we will review the two widely used forms of induction, complete (or strong) induction (also called course-of-values induction) and simple induction. We will see how they are utilized, and when one is more convenient than the other; relate them to each other, but also to another principle that is valid on natural numbers, the least (integer) principle.

#### 1.4.1   Complete, or Course-of-Values, Induction

Suppose that (n) is a “property”—that is, a formula of one free variable, n—of the natural number n. To prove that (n) holds for all n it suffices to prove for the arbitrary n that (n) holds.

What we mean by “arbitrary” is that we do not offer the proof of (n) for some specific n such as n = 42; or n even; or any n that has precisely 105 digits, etc. If the proof indeed has not cheated by using some property of n beyond the generic “

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

No credit card required