The Tower of Hanoi

The Tower of Hanoi puzzle was invented in 1883 by the French mathematician Édouard Lucas. He introduced the puzzle under the name "La Tour d'Hanoï", inspired by the then-exotic city of Hanoi, Vietnam. Lucas originally sold the puzzle as a toy under the pseudonym "Professor N. Claus (of Siam)", a playful anagram of Lucas d'Oncieu, a reference to his own name.

The puzzle was accompanied by a mythical legend:

In a temple in the Indian city of Benares (now Varanasi), priests are said to be moving 64 golden disks between three diamond pegs. According to the legend, when they finish, the world will end. This was a fictional narrative created by Lucas to popularize the puzzle, but it caught on and gave the Tower of Hanoi its mystique.

A more practical version of the puzzle however included the use of 8 disks.

This is a classical recursion puzzle that appears in computer science and mathematics curricula time and time again. Because it models the essence of recursive problem-solving, breaking a problem into smaller subproblems of the same form, the Tower of Hanoi continues to be a foundational exercise in algorithmic thinking.

When I was going through my undergrad, I could not fully grasp the concept of recursions and their "closed forms" until I understood the most basic puzzle. Hopefully, this blog serves the same purpose for you as Concrete Mathematics did for me.

The Puzzle and the Recurrence

The puzzle involves three pegs and n disks of distinct sizes. The objective is to move the entire stack from one peg to another, following these constraints:

The smaller disks can never be below the bigger ones.
You can only move 1 disk at a time.

This recurrence relation captures the recursive strategy: move n - 1 disks to an auxiliary peg (Tₙ₋₁ moves), move the largest disk (1 move), and move the n - 1 disks onto the largest disk again (Tₙ₋₁ moves). Thus, the total cost is 2Tₙ₋₁ + 1.

Motivation for a Closed-Form

As Concrete Mathematics notes:

The recurrence allows us to compute Tₙ for any n we like. But nobody really likes to compute from a recurrence, when n is large; it takes too long. […] A solution to the recurrence would make us much happier.

The goal is to find a closed-form expression for Tₙ, an explicit formula that allows computation of any value without relying on previous terms.

Transformation for simplification

To simplify the recurrence, the authors suggest an elegant transformation. Starting from:

Tₙ = 2Tₙ₋₁ + 1 we add 1 to both sides:

Tₙ + 1 = 2Tₙ₋₁ + 2 Now define a new sequence:

Uₙ = Tₙ + 1 Substituting this into the equation gives:

Uₙ = 2Uₙ₋₁ with U₀ = 1 This is a homogeneous recurrence relation with a well-known solution:

Uₙ = 2ⁿ Thus:

Tₙ = Uₙ - 1 = 2ⁿ - 1 This method avoids the need for guessing by using a change of variables that yields a simple recurrence.

Formal Proof via Mathematical Induction

To confirm the correctness of the formula Tₙ = 2ⁿ - 1, we use mathematical induction.

Base Case (n = 0):

T₀ = 0 = 2⁰ - 1 = 1 - 1 = 0 ✓ Inductive Hypothesis: Assume Tₖ = 2ᵏ - 1 holds for some k ≥ 0.

Inductive Step: Using the recurrence:

Tₖ₊₁ = 2Tₖ + 1 = 2(2ᵏ - 1) + 1 = 2ᵏ⁺¹ - 2 + 1 = 2ᵏ⁺¹ - 1 ✓ Hence, the formula holds for all n ≥ 0 by mathematical induction.

Why write this blog post?

The Tower of Hanoi is a classical recursion puzzle that appears in computer science and mathematics curricula time and time again. Its structure offers a natural introduction to:

Recursive function design
Recurrence relations
Mathematical induction
Algorithm analysis

Because it models the essence of recursive problem-solving, breaking a problem into smaller subproblems of the same form, the Tower of Hanoi continues to be a foundational exercise in algorithmic thinking.

My goal is to explore the actual computer science, the math, the logic, the structure and not the noise. I don’t want my favorite subject lost in the echo of AI “vibe coding.” I’ll be writing more about Concrete Mathematics as a way to reconnect with the joy I found learning to code, one proof and puzzle at a time.