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 investi- gated 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 Raise your hand a tower of eight disks,initially stacked in decreasing size on one of three pegs: if you've never seen this OK,the rest of you can cut to equation (1.1). The objective is to transfer the entire tower to one of the other pegs,moving only one disk at a time and never moving a larger one onto a smaller. Lucas 208furnished his toy with a romantic legend about a much larger Gold-wow. Tower of Brahma,which supposedly has 64 disks of pure gold resting on three Are our disks made diamond needles.At the beginning of time,he said,God placed these golden of concrete? disks on the first needle and ordained that a group of priests should transfer them to the third,according to the rules above.The priests reportedly work day and night at their task.When they finish,the Tower will crumble and the world will end.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 investi￾gated repeatedly by mathematicians; and their solutions all use the idea of recuvexe, in which the solution to each problem depends on the solutions to smaller instances of the same problem. Raise your hand if you’ve never seen this. OK, the rest of you can cut to equation (1.1). 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: The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller. Lucas [208] furnished his toy with a romantic legend about a much larger Gold -wow. Tower of Brahma, which supposedly has 64 disks of pure gold resting on three Are our disks made of concrete? diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. 1