Modeling the minimum number of moves in the Tower of Hanoi problem. [Concrete Mathematics Textbook]

107 Views Asked by At

I read the other related question but it doesn't quite answer my question.

"If Tn is the minimum number of moves for the Tower of Hanoi problem

T0 + 1 = 1;

Tn + 1 = 2Tn-1

Now if we let Un = Tn + 1 for n > 0

U0 = 1;

Un = 2Un - 1

It doesn't take a genius to discover that the solution to this recurrence is just Un = 2n "

I guess I'm not a genius because I don't understand that logical leap from 2Un-1 to 2n.