Day 17: CM, Page 4

One of the main objecties of this book is to explain how a person can solve recurrences without being clairvoyant.
- Concrete Mathematics p. 4

Day 17: The authors give an outline for solving problems like the Tower of Hanoi:

1. Look at small cases...
2. Find and prove a mathematical expression for the quantity of interest...
3. Find and prove a closed form for our mathematical expression...
- CM p.4

This is the approach we just went through yesterday for the Tower of Hanoi. The authors explain that the rest of the book is focused on helping us find closed forms without brilliant leaps of insight. They give an example of one technique: change the form of an equation to reveal underlying patterns.

Suppose U(n) = T(n) + 1. Then if we add one to both sides of our recurrence, we have:
T(0) + 1 = 1
T(n) + 1 = 2(T(n-1)) + 2 = 2(T(n-1) + 1)

So:
U(0) = 1
U(n) = 2(U(n-1))

After restructuring the problem slightly, it is clear that the closed form of U(n) is 2^n. So T(n) = U(n) -1 = 2^n - 1.

To rephrase the author's suggestion, when solving a problem like this, we need to:
1. Look at small cases
2a. Find some notation that provides an answer to the problem.
2b. Try to represent the solution so that the underlying pattern or structure is more apparent.
2c. Try to find a different way to look at the problem (e.g. binomial coefficients can be looked at probabilistically or as a summation).
3. Based on the tricks above (plus any others), find a closed form.

Tomorrow we'll look how to slice a pizza to achieve maximum slices.