Are there any starting and ending configurations of n disks

Are there any starting and ending configurations of n disks on three pegs that are more than 2ⁿ- 1 moves apart, under Lucas’s original rules?

Tower of hanoi problem.

Solution

Let P(n) be the proposition that to move from one arrangement to another following the rules of ToH, T(n)=number of moves required is less than or equal to 2^(n)-1.

P(0) is true since T(0)=0 and 2^(0)-1=0 and 0<=0 is true.

Assume P(n-1) is true. We will show the truth of the statement P(n):

For a starting configuration of n disks, the largest disk must be at the bottom of one of the 3 pegs. If this disk is in the peg where it should be at the end, we only need to move the other (n-1) disks to their final configuration. This will take T(n-1)=2^(n-1)-1 moves. And it is true that in this case T(n)=2^(n-1)-1<=2^(n)-1.

If the largest disk is not in the peg where it should be at the end, we first need to move the other (n-1) disks to the 3rd remaining peg which takes T(n-1) moves, then transfer the largest peg to its final position in 1 move, and then transfer the (n-1) disks from their current positions to their final position in T(n-1) moves. Hence T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1=2(2^(n-1)-1)+1=2^(n)-1

Hence, by induction T(n)<= 2^(n)-1.