---
title: "Derive and solve Tower of Hanoi recurrence"
subject: "Discrete Structure"
chapter: 3
key: "semester_4/discrete_structure:hanoi-derive-and-solve"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/hanoi-derive-and-solve
site: BCT Engineering
---

# Derive and solve Tower of Hanoi recurrence

Discrete Structure · Chapter 3: Recurrence Relation

- Asked in: 2070 Bhadra, 6 marks
- Video: [Tower of Hanoi Problem - Made Easy](https://www.youtube.com/watch?v=q6RicK1FCUs) — Abdul Bari
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/hanoi-derive-and-solve
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-3

## Question

Derive and solve the recurrence relation for Tower of Hanoi puzzle.

## Short answer

The recurrence H_n = 2H_{n-1} + 1, H_1 = 1, is derived by moving the top n-1 discs twice and the largest once. Solving by iteration or characteristic method gives H_n = 2^n - 1.

## Answer

#### Deriving the recurrence
Let Hₙ be the least number of moves to transfer n discs from peg A to peg C using peg B.
- Move the top n − 1 discs A → B: Hₙ₋₁ moves.
- Move the biggest disc A → C: 1 move.
- Move the n − 1 discs B → C: Hₙ₋₁ moves.

So **Hₙ = 2Hₙ₋₁ + 1**, with H₁ = 1 (one disc needs one move). This is also the minimum, because the largest disc must move at least once, and for that move the other n − 1 discs must already be on one other peg, which takes at least Hₙ₋₁ moves, and they must be moved again after.

#### Solution 1: iteration (backward substitution)
```text
Hₙ = 2Hₙ₋₁ + 1
   = 2(2Hₙ₋₂ + 1) + 1 = 2²Hₙ₋₂ + 2 + 1
   = 2²(2Hₙ₋₃ + 1) + 2 + 1 = 2³Hₙ₋₃ + 2² + 2 + 1
   ...
   = 2ⁿ⁻¹H₁ + (2ⁿ⁻² + ... + 2 + 1)
   = 2ⁿ⁻¹ + (2ⁿ⁻¹ - 1) = 2ⁿ - 1
```

#### Solution 2: characteristic method
- Homogeneous: Hₙ = 2Hₙ₋₁, so r = 2 and Hₙ⁽ʰ⁾ = α·2ⁿ.
- Particular: F(n) = 1, try Hₙ⁽ᵖ⁾ = c: c = 2c + 1 gives c = −1.
- General: Hₙ = α·2ⁿ − 1. Using H₁ = 1: 2α − 1 = 1 gives α = 1.

**Answer: Hₙ = 2ⁿ − 1**

For example, 3 discs need 7 moves, 10 discs need 1023, and 64 discs need 2⁶⁴ − 1 moves.

## Check yourself

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

1. What is the order of the strategy?
   A. Move n−1 discs to B, move the largest to C, move the n−1 discs onto C
   B. Move largest to B, then others to C
   C. Move n−1 discs to C, then the largest to B
   D. Move all discs one at a time to B
   Answer: A. The largest disc needs the other n−1 on a different peg. (Key point: Three steps)

2. Why can't fewer moves work?
   A. Larger discs can't be moved
   B. The largest disc must move, which requires n−1 discs on another peg and later moved again
   C. Each disc moves exactly twice
   D. Pegs are limited to 2
   Answer: B. At least H(n−1) before and H(n−1) after. (Key point: Why minimal)

3. Which particular constant solves H_n = 2H_(n−1) + 1?
   A. c = 1
   B. c = 0
   C. c = −1
   D. c = 2
   Answer: C. c = 2c + 1 gives c = −1. (Key point: Particular solution)

4. What is H_n?
   A. 2^n − 1
   B. 2^n
   C. n^2
   D. 2^(n−1)
   Answer: A. α·2^n − 1 with H1 = 1 gives α = 1. 10 discs need 1023 moves. (Key point: Final solution)

## Related in Discrete Structure

- [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — 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