Tower of Hanoi

Discrete Math · Axiom Academy

REAL WORLD Tower of Hanoi: Deriving Recurrence Relations Play the classic puzzle, discover its recursive pattern, and derive the mathematical formula T(n) = 2ⁿ - 1 The Tower of Hanoi is a mathematical puzzle invented in 1883. The objective is simple: move all disks from the leftmost peg to the rightmost peg, following two rules: Never place a larger disk on top of a smaller disk Try solving the puzzle below! Click a disk to select it, then click the destination peg. Start with 3 disks to get a feel for it. Goal: Try different numbers of disks and pay attention to the minimum number of moves required. Is there a pattern? Now that you've experimented with the puzzle, let's think about the minimum number of moves needed for different numbers of disks. What is the minimum number of moves required to solve the Tower of Hanoi with n = 3 disks? The key insight is that the Tower of Hanoi has a recursive structure . To move n disks from peg A to peg C: Step 1: Move the top (n-1) disks from A to B (using C as auxiliary) Step 2: Move the largest disk from A to C Step 3: Move the (n-1) disks from B to C (using A as auxiliary) This gives us a recurrence relation ! If T(n) represents the minimum number of moves for n disks, then: Key Idea: We solve a problem of size n by solving two problems of size (n-1), plus one additional move for the largest disk. Now let's use our recurrence relation to find the exact formula. We know: with the base case T(1) = 1 (moving a single disk takes 1 move).

This is the written version of the interactive lesson above. See the full Discrete Math course.