I have a question that follows:
Consider a Double Tower of Hanoi. In this variation of the Tower of Hanoi there are three
poles in a row and 2n disks, two of each of n different sizes, where n is any positive integer.
Assume one of the poles initially contains all of the disks placed on top of each other in pairs
of decreasing size. Disks are transferred one by one from one pole to another, but at no time
may a larger disk be placed on top of a smaller disk. However, a disk may be placed on top
of one of the same size. Let a(n) be the minimum number of moves needed to transfer a tower
of 2n disks from one pole to another.
I understand the concept of the usual towers problem. Where if you have n disks, to find out how many moves it requires to move the whole tower, you need to move n-1 disks, the nth disk, and then n-1 disks again. n-1 has a certain amount of moves in it.
So far i have managed to work out for the double tower of hanoi that:
a1 = 1 (one disk to move)
a2 = 2 (two disks to move and since they are the same size the action ends after the second disk is moved)
a3 = 5
a4 = 6
a5 = 13
a6 = 14
a7 = 29
a8 = 30.
The recurrence relations i've worked out are:
for a(2k) = a(k-2) + 2 + a(k-2)
= 2(a(k-2)) + 2
a(2k+1) = a(k-1) + 1 + a(k-1)
= 2(a(k-1)) + 1
(also sorry that the indentation isn't correct, i'm not sure how to do that here).
I'm a little lost on whether or not my answer is correct in finding the recurrence relation.
Also the next part of the question states:
Show that the formula an = 2^(n+1) – 2 for the nth term in the sequence satisfies the recurrence relation you derived in (b).
Which completely throws me. What is the formula used for? I thought the recurrence relation would give me the answer to: "how many moves does it take to move N disks", what is this second formula for?
If possible, would appreciate an explanation without an answer, maybe using the original tower of hanoi problem. Although i understand if thats not possible.
Best Answer
This seems to be taken from "Discrete Mathematics with Applications" by Susanna S. Epp, Exercise Set 5.6 (page 303 - Question 21). What I noticed was that when you move discs of size k you can view them as if they were one disc of size k. The difference is that it takes double the number of moves to move the 2 discs as compared to just one.
Therefore, the solution uses the same logic as moving k discs from one pole to another. That is the problem posed in Question 18, that has the adjancency requirement. So you would take the recurrence relation that you derive for that question and double the answer.
i.e: $t_k := 2b_k = 2(a_{k-1} + 1 + b_{k-1}) = 2a_{k-1} + 2 + 2b_{k-1} \ for \ k \geq 2 $
Also, you could simplify this using what 17(e) asks you to prove: $b_k := 3b_{k-1} + 1 \implies t_k := 2(3b_{k-1} + 1) = 6b_{k-1} + 2$