## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

 CHAPTER 2 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required