# Thread: Towers of Hanoi Adjacent

1. ## Towers of Hanoi Adjacent

How can this recurrence be done?

Towers of Hanoi with an Adjacency Requirement: Suppose that the monks
moving those disk in Hanoi are further restricted to only move a disk from one pole to an adjacent
one –in addition to the standard limitations for this problem. Assume poles
A and C are at two
ends of a row, and pole
B is in the middle. Find a recurrence relation for ak: the minimum number

of moves needed to transfer a tower of
k disks from pole A to pole C.

2. Also how do I prove these recursion:
1. C(n, 0) + C(n-1, 1) + C(n-2, 2) + ... = F_{n+1}

2. C(n, 1) F_1 + C(n, 2) F_2 + ... + C(n, n) F_n = F_{2n} with a combinatorial argument,for any natural numbers n>=1

3. Find a recurrence that answers the following question:
How many sequences of length n are there that use digits 0,1,2, and
3 and have an even number of 0's?

### adjacent tower of hanoi

Click on a term to search for related topics.