Hey,

I need the reccurence relation equation for question C.

Here is what I think it is:

sk = sk-1 +3 + sk-1

because s1=1, s2=1+1+1=3

s3=s1 +(1+1+1) + s1 =5

s4=s2 + (1+1+1)+s2=9

Am I correct with the reccurence relation equation? BTW do I need this for question c?

The problem is as follows:

1. Four-pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a larger disk be placed on a smaller disk. Let sk be the number of moves to transfer an entire tower of k disks from the left-most pole (A) to the right-most pole (D).

a. Find s1, s2, and s3.

b. Find s4.

c. Show that sk <= 2sk-2 + 3 for all integers k>=3.