Day 15: CM, Page 2

... we'll see repeatedly in this book that it's advantageous to LOOK AT SMALL CASES first.
- Concrete Mathematics p.2

The next step in solving the problem is to introduce appropriate notation: NAME AND CONQUER.
- Concrete Mathematics p.2

Day 15: Two of the most important tools in problem solving are introduced: look at small cases and find a good notation. Looking at small cases is especially important. This is useful for problem solving in almost any context. It's often easy to spot patterns by examining the simplest cases first.

For Tower of Hanoi problem, the authors note that T(1) = 1 (it takes one move to move one disk), T(2) = 3 (it takes three moves to move two disks) and T(0) = 0 (it takes no move to move no disks). How would we move three disks? We already have a way to move 2 disk, so first we would move two disks, then we would move the third disk, and finally we would move the two disks back onto the third. This is a recursive solution. If we can solve the problem for T(n-1), we can solve it for T(n).

The authors use the observation above to show that T(n) <= 2(T(n-1)) + 1. This is true, because we can move the top n-1 disks to one peg, move the bottom disk, then move the n-1 disks onto the bottom disk. We know this solution takes 2(T(n-1)) + 1 moves, but maybe there is a solution that takes fewer moves? Nope. The authors point out that when we move the nth disk, the other n-1 disks must be on another peg. So in the best case, we still need to move n-1 pegs to the other disk. There's no other option. So T(n) >= 2(T(n-1)) + 1 (it's possible you could do worse than 2(T(n-1)) + 1 if you make bad moves).

That's it for page 2. More on the Tower of Hanoi tomorrow.