Course contentsShow
← Mathematics
Lesson 2637 of 3,12152. CombinatoricsFree lesson

Applications: Tower of Hanoi and Counting Problems

Apply recurrence relations to solve classic problems including Tower of Hanoi and combinatorial counting scenarios.

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:

  1. Move the top n-1 disks to the spare peg
  2. Move the largest disk to the destination
  3. 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.