2ⁿ−1 · The Tower of Hanoi
The Tower of Hanoi
Three pegs, disks of different sizes. You may move one disk at a time, and a larger disk can never sit on a smaller one. What is the fewest moves to shift a 3-disk tower to another peg?
The legend of 64 golden disks — finish moving them, and the world ends.
Think about it first
Make a prediction first. Change one input at a time and compare what happens with what you expected.
Rules: one disk at a time · a larger disk never sits on a smaller one. Tap a peg to pick up its top disk, tap another peg to drop it.
Tap a peg to pick up its top disk.
Read the solution when you are ready
The Tower of Hanoi is not a moving problem — it is a splitting problem.
Why does this question matter?
The Tower of Hanoi was invented in 1883 by the French mathematician Édouard Lucas. The tale of Brahmin priests moving 64 golden disks — 'when they finish, the world ends' — was a legend Lucas made up to package the puzzle.
The puzzle has survived 140+ years not for its answer but for its method. There is no way to move n disks at once. But the moment you think 'first clear the n−1 disks above', the big problem becomes the same problem one size smaller.
Thinking that splits a problem into a smaller copy of itself is called recursion. It is the backbone of how computers sort and search huge data. The Tower of Hanoi is the oldest hands-on lab for recursion.
Read the idea from another angle
You don't need to know how to move n disks — only n−1.
Clear the top n−1 disks to the spare peg, move the bottom disk, and stack the n−1 back on. Instead of solving the big problem, you delegate to a smaller one. That delegation is all recursion is.
When doubling repeats, human intuition always loses.
Double per disk: ten disks is a thousand moves, twenty is a million, and 64 is 40 times the age of the universe. Only someone who has felt exponential explosion avoids the 'it'll be quick' trap.
Now read the definitions with their conditions
Let's translate what you discovered into symbols. Call the minimum for n disks M(n); the clear-move-restack routine your hands just performed becomes the formula itself.
Formula anatomy — the three hand motions become the equation
= + +
Recurrence (the split)
The answer for n is twice the answer for n−1, plus one. This is the moment the big problem splits into a smaller one.
Closed form
Unroll the recurrence all the way and this single line remains. 1, 3, 7, 15, 31, … each one less than a power of two.
The time for 64 disks
Even at one move per second, that is over 40 times the age of the universe. That is why the legend says the world ends.
Make one more distinction
One more disk means just a few more moves.
It grows by multiplication, not addition. Each extra disk roughly doubles the minimum, because the n−1 disks above must be moved twice. Three disks take 7 moves; ten disks already take 1,023.
64 disks? Just move fast and it's done.
At one move per second, nonstop, it takes about 585 billion years — over 40 times the age of the universe (about 13.8 billion years). Diligence cannot beat an exponential.
Where else can this idea help?
Divide-and-conquer algorithms
To sort a million records, a computer splits them in half again and again, sorts the small pieces, and merges (merge sort). It is exactly the Hanoi habit of delegating to a smaller copy of the problem.
Every programmer's first recursion
The Tower of Hanoi is the classic first example when programming courses teach recursive functions, because it shows a function calling itself in a way you can watch.
Backup tape rotation
A classic scheme for rotating server backups is literally called the 'Tower of Hanoi' rotation. It borrows the disks' rhythm — disk 1 moves every 2nd turn, disk 2 every 4th.
Problem-solving research in psychology
Cognitive psychology and neuroscience use the Tower of Hanoi to measure planning ability, because it exposes how far ahead a person can set intermediate goals.
Explain it in your own words
Check the idea with practice problems (4)
Questions completed 0 / 4
1. What is the minimum number of moves for 4 disks?
2. Why is the minimum M(n) = 2M(n−1) + 1?
3. What is the minimum number of moves for 5 disks?
4. When one more disk is added, the minimum number of moves…
What question comes next?
Previous concept
Exponentiation
Feel how fast repeated doubling grows first, and the weight of 2ⁿ − 1 becomes visible.
← Exponentiation labLeads to next
The Hundred Doors
Next problem — which doors stay open after 100 people toggle them? This time divisors take the stage.
Go to the The Hundred Doors lab →Related lab
Sequences
Recurrences like M(n) = 2M(n−1) + 1 — the grammar of building each term from the last lives here.
Go to the Sequences lab →Related lab
The Chessboard & Rice
Doubling per square — the same 2ⁿ explosion that bankrupted a king.
Go to the The Chessboard & Rice lab →