Applications: Tower of Hanoi and Counting Problems
What you'll learn: How to apply recurrence relations to solve classic problems like the Tower of Hanoi puzzle and combinatorial counting scenarios.
The Core Idea
Recurrence relations aren't just abstract formulas—they're powerful tools for solving real problems where solutions build on smaller versions of the same problem. Two classic applications demonstrate this beautifully.
Tower of Hanoi
Imagine three pegs and n disks of different sizes stacked largest-to-smallest on one peg. The goal: move all disks to another peg, moving one disk at a time, never placing a larger disk on a smaller one.
To move n disks:
- Move the top n-1 disks to the spare peg
- Move the largest disk to the destination
- Move those n-1 disks from spare to destination
If T(n) represents the minimum moves needed for n disks:
- T(n) = 2T(n-1) + 1 (two recursive sub-problems plus one move)
- T(1) = 1 (base case)
Solving this recurrence gives T(n) = 2ⁿ - 1. For 64 disks, that's over 18 quintillion moves!
Counting Problems
Recurrence relations also count sequences with constraints. For example: "How many binary strings of length n contain no consecutive 1s?"
Let a(n) be this count. Any valid string of length n either:
- Ends in 0: the first n-1 digits can be any valid string → a(n-1) ways
- Ends in 1: must be preceded by 0, so first n-2 digits are any valid string → a(n-2) ways
Thus a(n) = a(n-1) + a(n-2) with a(1) = 2, a(2) = 3—producing the Fibonacci sequence!
Key Takeaway: Recurrence relations transform complex problems into manageable recursive structures by expressing solutions in terms of smaller instances, making seemingly intractable puzzles and counting problems solvable through systematic decomposition.