1. Recurrent Problems
This chapter explores three sample problems that give a feel for what’s to come. They have two traits in common: They’ve all been investigated repeatedly by mathematicians; and their solutions all use the idea of recurrence, in which the solution to each problem depends on the solutions to smaller instances of the same problem.
1.1 The Tower of Hanoi
Let’s look first at a neat little puzzle called the Tower of Hanoi, invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:
Raise your hand if you’ve never seen this. OK, the rest ...