Recall that if n is any nonnegative integer and an is the mi

Recall that if n is any non-negative integer, and an is the minimum number of moves
needed to solve the Tower of Hanoi puzzle with n disks, then a_n+1=1+2_an and a_n=(2^n)-1.

But notice that these formulas both make sense if n is any integer, even if n is negative.
Allowing n to be any integer yields the bilateral sequence ...,a_-3=-7/8, a_-2=-3/4, a_-1=-1/2, a_0=0, a_1=1, a_2=3, a_3=7,...

which extends indenitely in either direction. The terms of the sequence indexed by the non-negative integers have a meaning: they correspond to the minimum number of moves needed to solve the Tower of Hanois puzzle with a non-negative number of disks. Can you give the terms indexed by the negative integers a meaning too?

Solution

We know the number of disks cannot be and we observe that if there are n disks then it requires 2^n-1 moves to solve the Tower of Hanoi.

If n is a negative integer then there exist and integer m>0 such that n=-m

then we have a_n=2^n-1=2^(-m)-1=1/2^m-1=(1-2^m)/2^m

Then the absolute value of the numerator that is |1-2^m| or -(2^m-1) gives the number of moves required to solve the Tower of Hanoi, if the are m disks.

Thus, the terms indexed by negative integers have a meaning, the negative of the numerator gives the minimum number of moves required to solve the Tower of Hanoi with a negative number of disks.