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 “
Get Theory of Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
