Derive and solve Tower of Hanoi recurrence

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)

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.