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

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 “

Start Free Trial

No credit card required