O'Reilly logo

Concrete Mathematics: A Foundation for Computer Science, Second Edition by Oren Patashnik, Donald E. Knuth, Ronald L. Graham

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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:

Image

Raise your hand if you’ve never seen this. OK, the rest ...

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

Start Free Trial

No credit card required