Well the original question was asking about Tower of Hanoi. First I need to come up with a recurrence for the Tower of Hanoi with 4 poles. (Please note the original tower only consist of 3 poles)
The recurrence I came up with is $T(n)=2*T(n-2)+3$
Then part b of the question ask me to show that the recurrence I came up with satisfy $T(n)=O(2^{n/10})$. Doesn't have a clue how to show this.
On
You'll have to seperate each case n odd, n even.
If n is even, define: $ U_p = T_{2p} = T_n $
You get : $ U_p = 2U_{p-1} + 3 $
Dividing by $2^p$ and setting $V_p = \frac{U_p}{2^p}$ you get:
$ V_p = V_{p-1} + \frac{3}{2^p} $
Telescoping the $V_p$ you get :
$ V_p -V_o = 3\sum_{k=1}^p \frac{1}{2^k} = \frac{3}{2}\frac{1-\frac{1}{2^p}}{1-\frac{1}{2}} = 3(1-2^{-p}) $
You end up with : $T_{2p} = U_p =2^p*V_p = 3(2^p-1) +2^p*T_o$
From here it's not very difficult. You can do the same defining $U_p = T_{2p+1}$ when n is odd, n=2p+1
I'm not really sure about this recurrence and the Hanoi tower, but an easy way to solve it is using difference equations: $$ T_{n-1} = 2 T_{n-3} + 3 $$ Now subtract this equation from the one in your question and denote $\Delta T_n = T_n - T_{n-1}$ and work your way to $\Delta T_1$. Then sum over $n$ and on LHS you'll have most terms cancelling out. Can you handle from here?