In a Double Tower of Hanoi with Adjacency Requirement there are three poles in a row and
2n disks, two of each of n diﬀerent sizes, where n is any positive integer. Initially pole A (at
one end of the row) contains all the disks, placed on top of each other in pairs of decreasing
size. Disks may only be transferred one-by-one from one pole to an adjacent pole and at no
time may a larger disk be placed on top of a smaller one. However a disk may be placed on
top of another one of the same size. Let C be the pole at the other end of the row and let $$s _ { n } = \left[ \begin{array} { l }
\text { the minimum number of moves } \
\text { needed to transfer a tower of } 2 n \
\text { disks from pole } A \text { to pole } C
\end{array} \right]$$
(a) Find $s _ { 1 }$ and $s _ { 2 }$.
(b) Find a recurrence relation expressing $s _ { k }$ in terms of $s _ { k - 1 }$ for all integers $k \geq 2$. Justify your answer carefully.

Question

In a Double Tower of Hanoi with Adjacency Requirement there are three poles in a row and
2n disks, two of each of n diﬀerent sizes, where n is any positive integer. Initially pole A (at
one end of the row) contains all the disks, placed on top of each other in pairs of decreasing
size. Disks may only be transferred one-by-one from one pole to an adjacent pole and at no
time may a larger disk be placed on top of a smaller one. However a disk may be placed on
top of another one of the same size. Let C be the pole at the other end of the row and let $$s _ { n } = \left[ \begin{array} { l } 
\text { the minimum number of moves } \
\text { needed to transfer a tower of } 2 n \
\text { disks from pole } A \text { to pole } C
\end{array} \right]$$ 
 (a) Find $s _ { 1 }$ and $s _ { 2 }$.
(b) Find a recurrence relation expressing $s _ { k }$ in terms of $s _ { k - 1 }$ for all integers $k \geq 2$. Justify your answer carefully.

Quizplus · Accepted Answer

The Answer of In a Double Tower of Hanoi with Adjacency Requirement there are three poles in a row and
2n disks, two of each of n diﬀerent sizes, where n is any positive integer. Initially pole A (at
one end of the row) contains all the disks, placed on top of each other in pairs of decreasing
size. Disks may only be transferred one-by-one from one pole to an adjacent pole and at no
time may a larger disk be placed on top of a smaller one. However a disk may be placed on
top of another one of the same size. Let C be the pole at the other end of the row and let $$s _ { n } = \left[ \begin{array} { l } 
\text { the minimum number of moves } \
\text { needed to transfer a tower of } 2 n \
\text { disks from pole } A \text { to pole } C
\end{array} \right]$$ 
 (a) Find $s _ { 1 }$ and $s _ { 2 }$.
(b) Find a recurrence relation expressing $s _ { k }$ in terms of $s _ { k - 1 }$ for all integers $k \geq 2$. Justify your answer carefully.

In a Double Tower of Hanoi with Adjacency Requirement There