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 “