Induction and Recursion
This chapter presents two very powerful techniques for defining infinite sequences (recursion) and proving properties of infinite sequences (induction). The sequences in which we are interested are not only sequences of numbers (e.g., even positive integers) but also sequences of more elaborate objects (e.g., digital circuits).
Suppose we wish to define the even numbers. Typically, one could write 0, 2, 4, … This informal description assumes that the reader can guess how the sequence continues and how to generate the next number in the sequence. (The next number is 6!) A more systematic way to describe a sequence x0, x1, x2, … is to build a “device” that when input an element xn of the sequence, outputs ...