The Tower of Hanoi

Recurrent Problems - The Tower of Hanoi

T_n is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules.

small cases

T₀ = 0, T₁ = 1, T₂ = 3 .....

mathematical expression

T₀ = 0, T_n = 2T_{n - 1} + 1, for n > 0

closed form

T_n = 2ⁿ - 1, for n >= 0