Question

Suppose the Tower of Hanoi rules are changed so that stones may only be transferred to an adjacent clearing in one move. Let In be the minimum number of moves required to transfer tower from clearing A to clearing C? For example, it takes two moves to move a one stone tower from A to C: One move from A to B, then a second move from B to C. So I1 = 2

Answer 1

Answer:

$l_n=3^n-1$

Step-by-step explanation:

We will prove by mathematical induction that, for every natural n,  

$l_n=3^n-1$

We will prove our base case (when n=1) to be true:

Base case:

As stated in the qustion, $l_1=2=3^1-1$

Inductive hypothesis:  

Given a natural n,  

$l_n=3^n-1$

Now, we will assume the inductive hypothesis and then use this assumption, involving n, to prove the statement for n + 1.

Inductive step:

Let´s analyze the problem with n+1 stones. In order to move the n+1 stones from A to C we have to:

1. Move the first n stones from A to C ($l_n$ moves).
2. Move the biggest stone from A to B (1 move).
3. Move the first n stones from C to A ($l_n$ moves).
4. Move the biggest stone from B to C (1 move).
5. Move the first n stones from A to C ($l_n$ moves).

Then,

$l_{n+1}=3l_n+2$.

Therefore, using the inductive hypothesis,

$l_{n+1}=3l_n+2=3(3^n-1)+2=3^{n+1}-3+2=3^{n+1}-1$

With this we have proved our statement to be true for n+1.    

In conlusion, for every natural n,

$l_n=3^n-1$