Double Tower of Hanoi Puzzle: Minimum Moves & Recurrence Relation

[hansel13]

The double tower of Hanoi puzzle contains 2n discs. There are n different sizes, two
of each size. Initially one of the poles contains all the disks placed on top of each other in decreasing size. Discs of the same size are identical. You are allowed to
place discs of the same size on top of each other. Let an be the minimum number of moves
need to solve the puzzle. Find a recurrence relation for a₁, a₂, a₃, ...

This is what I came up with, and wanted to see if it was right:
a₁ = 3
a_n = 2a_n-1 + 2.

Is this correct?
thanks

 

[bpet]

Perhaps you could explain how the recurrence relation was obtained?

 

[hansel13]

Well a1 = 3 because When n is 1, we have 2 discs. There are 3 moves to get the discs to the other peg (1,2,1)

And I have problems trying to figure the the recurrence relation, not sure how to find it from the information we are given.

 

[Moo Of Doom]

Why is a₁ = 3? Can't you solve it in two moves by moving the discs one after the other to the target rod? Since the two discs are "identical," this should be a solution, right? Or are the discs also labeled, and need to be stacked in the same exact order on the target rod?

Also, I have no idea how to read your notation for moving the discs.

 

[HallsofIvy]

I see nothing difficult about this problem. You start with the disks in order of size, so each pair of disks of the same size is together. Once you move the top disk of such a pair, you can, and should, immediately move the next disk on to of it. Thus, we can think of each "pair" as a single disk and are back to the original problem. The only difference is that it takes 2 moves to move each pair. The number of moves is just 2 times the number of moves in "single" Towers of Hanoi, $2(2^n- 1)= 2^{n+1}- 2$.

 

[hansel13]

Why is a₁ = 3? Can't you solve it in two moves by moving the discs one after the other to the target rod? Since the two discs are "identical," this should be a solution, right? Or are the discs also labeled, and need to be stacked in the same exact order on the target rod?

Also, I have no idea how to read your notation for moving the discs.

Sorry, cleaned up my notation. Got myself mixed up with another problem when I was writing up the problem. EDITED.

And I understand now. I thought by 2n, we had 2n different sizes. I should have read the instructions better.

so assuming we start on the leftmost peg...
a₁ = 2 (Move first disc to adjacent peg. Move second disc on top of first disc because they are the same size.)
a₂ = 6
(Move Disc1 to middle peg.
Move Disc 2 to middle peg on top Disc1.
Move Disc 3 to right peg.
Move Disc 4 to right peg on top of Disc 3.
Move Disc 2 to the right peg on top of Disc 3 and 4.
Move Disc 1 to the right peg on top of Disc 2, 3 and 4.)

I think I got it now.