In the Tower of Hanoi game let Wn denote the minimum number

In the Tower of Hanoi game, let W_n denote the minimum number of moves needed to transfer n disks from one tower to another tower when there are four towers instead of three. Show that W_m lessthanorequalto 2 middot W_m-k + 2^k -1, for 0 lessthanorequalto k lessthanorequalto m. Show that W_n(n+1)/2 lessthanorequalto 2^n(n - 1) + 1, for all n greaterthanorequalto 0.

Solution

”The Tower of Hanoi”, Its solution uses the idea of recurrence, in which the solution to the problem depends on the solutions to smaller instances of the same problem. The puzzle was invented by the French mathematician Edouard Lucas in 1883. Lucas is known for his study of the Fibonacci sequence.

Let us consider the case if there are n disks. It is advantageous to look at small cases first. It is easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. We denote Tn the minimum number of moves that will transfer n disks from one peg to another under Lucas’s rules. Clearly T0 = 0, because no moves at all needed to transfer a tower of “0” disks. T1 = 1 (the middle peg is not at all used to transfer “1” disk) T2 = 3 (transfer the top disk to the middle peg, then move the second, then bring the smaller disk onto it).

We discuss the case of transfering a tower of 3 disks : 1. transfer the top 2 disks to the middle peg (requiring 3 moves) 2. move the largest disk to the third peg (requiring 1 move) 3. transfer the other two onto the largest disk (requiring 3 moves). This gives us a clue of transfering n disks in general : 1. transfer the top n 1 smaller disks to the middle peg (requiring Tn1 moves) 2. move the largest disk to the third peg (requiring 1 move) 3. transfer the n 1 smallest onto the largest disk (requiring Tn1 moves).

Thus we can transfer n disks (n > 0) in at most 2Tn1 + 1 moves :

Tn 2Tn1 + 1, for n > 0. (1)

That is, 2Tn1 + 1 moves suffice. Are 2Tn1 + 1 moves necessary? At some point we must move the largest disk to the third peg. When we do, the n 1 smallest must be on the middle peg, and it has taken at least Tn1 moves. At least 1 move is required to move the largest disk. After moving the largest disk, we again require at least Tn1 moves. Hence

Tn 2Tn1 + 1, for n > 0. (2)

From (1) and (2), together with the trivial solution for n = 0, yield T0 = 0 (boundary value) Tn = 2Tn1 + 1 for n > 0. The above set of equalities is called a recurrence (recursion) relation. Note that the general value Tn is in terms of earlier ones Tn1.