O'Reilly logo

Theory of Computation by George Tourlakis

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

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 Images(n) is a “property”—that is, a formula of one free variable, n—of the natural number n. To prove that Images(n) holds for all n Images Images it suffices to prove for the arbitrary n that Images(n) holds.

What we mean by “arbitrary” is that we do not offer the proof of Images(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.

Start Free Trial

No credit card required