Set up recurrence for Tower of Hanoi

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.

 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.