2 - Induction and Recursion

Summary

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 x₀, x₁, x₂, … is to build a “device” that when input an element x_n of the sequence, outputs the next element x_n+1. In the case of the sequence of even numbers, this device simply adds +2, that is, x_n+1 = x_n + 2. Of course, we need to define the first element x₀ in the sequence to be zero. Once we have defined x₀ and the device for determining x_n+1 based on x_n, 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 x₀ = 0 and x_n+1 = x_n + 2 is divisible by 2.