---
title: "Set up recurrence for Tower of Hanoi"
subject: "Discrete Structure"
chapter: 3
key: "semester_4/discrete_structure:hanoi-setup-recurrence"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/hanoi-setup-recurrence
site: BCT Engineering
---

# Set up recurrence for Tower of Hanoi

Discrete Structure · Chapter 3: Recurrence Relation

- Asked in: 2073 Magh, 5 marks
- Video: [The Tower of Hanoi (Recursive Formula and Proof by Induction)](https://www.youtube.com/watch?v=boS4N1_TLBk) — Florian Ludewig
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/hanoi-setup-recurrence
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3

## Question

Setup a recurrence relation for the sequence representing the number of moves needed to solve Hanoi Tower puzzle.

## Short answer

For n discs, the minimum number of moves H_n satisfies H_n = 2H_{n-1} + 1 for n ≥ 2, with H_1 = 1.

## Answer

**Puzzle:** n discs of different sizes are on peg A, largest at the bottom. Move all to peg C using peg B, moving one disc at a time and never placing a larger disc on a smaller one.

Let **Hₙ** be the minimum number of moves for n discs.

#### Setting up the recurrence
1. Move the top n − 1 discs from A to B (using C): Hₙ₋₁ moves.
2. Move the largest disc from A to C: 1 move.
3. Move the n − 1 discs from B to C (using A): Hₙ₋₁ moves.

```text
 Step 1: top n-1 discs  A -> B   (Hn-1 moves)
 Step 2: largest disc   A -> C   (1 move)
 Step 3: n-1 discs      B -> C   (Hn-1 moves)

  A        B        C
 [1]
 [2]                          start (n = 3)
 [3]
  A        B        C
 [3]      [1]
          [2]                 after step 1
  A        B        C
          [1]      [3]
          [2]                 after step 2
```
Hence

**Hₙ = 2Hₙ₋₁ + 1, for n ≥ 2, with H₁ = 1** (or H₀ = 0).

It is a linear non-homogeneous recurrence of order 1. Values: H₁ = 1, H₂ = 3, H₃ = 7, H₄ = 15, H₅ = 31. Solving it by repeated substitution gives Hₙ = 2ⁿ − 1.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many moves does the largest disc need in the strategy?
   A. n − 1 moves
   B. 1 move
   C. H(n−1) moves
   D. 2 moves
   Answer: B. The largest disc moves once from A to C. (Key point: Step count)

2. What is the recurrence for H_n?
   A. H_n = H_(n−1) + 1
   B. H_n = 2H_(n−1)
   C. H_n = 2H_(n−1) + 1
   D. H_n = H_(n−1) + H_(n−2)
   Answer: C. Move n−1 discs twice plus the large disc once. (Key point: Recurrence)

3. What is H_3?
   A. 6
   B. 8
   C. 5
   D. 7
   Answer: D. H_3 = 2(3) + 1 = 7. (Key point: Values)

## Related in Discrete Structure

- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3
- [What is a recurrence relation](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-relation-definition) — Discrete Structure, chapter 3, asked 2×
- [Solve third-order recurrence with n·4ⁿ](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Arecurrence-third-order-n-4-power-n) — Discrete Structure, chapter 3, asked 6×

## Related in other subjects

- [Recursion tree for Tower of Hanoi, 4 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-recursion-tree-4-disks) — Data Structure and Algorithm, chapter 5