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 the next element xn+1. In the case of the sequence of even numbers, this device simply adds +2, that is, xn+1 = xn + 2. Of course, we need to define the first element x0 in the sequence to be zero. Once we have defined x0 and the device for determining xn+1 based on xn, the sequence is well defined. This, in a nutshell, is recursion. In this book, we will use recursion to define sequences of circuits. In the meantime, we establish the topic of recursion on sequences of numbers. Suppose we wish to prove that each number in the sequence defined recursively by x0 = 0 and xn+1 = xn + 2 is divisible by 2.