# Homework Help: Recurrence relation proof

1. Mar 25, 2015

### toothpaste666

1. The problem statement, all variables and given/known data
prove that
$s_k <= 2s_{k-2}+3$
for all ints k >= 3
if s1=1 and s2 = 3 and s2=5 and s4=9

3. The attempt at a solution
base case k = 3
$s_3 <= 2s_1 + 3$
5 <= 2+3
that is true. Now i must prove the inductive step. This is where I am having trouble.
I assume that $s_k <= 2s_{k-2}+3$
and must prove that
$s_{k+1} <= 2s_{k-1}+3$
if i call m = k+1
then k-1 = m-2 and we have
$s_m <= 2s_{m-2}+3$
I am kinda confused though and I don't know if that proves something I didnt already know

2. Mar 25, 2015

### haruspex

Your question makes no sense. The sequence has not been defined.

3. Mar 25, 2015

### toothpaste666

It is supposed to be a tower of hanoi problem with 4 poles instead of 3 and k is the number of disks and sk is the number of moves it takes to move those disks

4. Mar 25, 2015

### haruspex

In that case you need to think up some reasonable algorithm for moving k disks, based on two sequences of moving k-2 disks.

5. Mar 25, 2015

### toothpaste666

should I use induction or was i heading in the wrong direction?

6. Mar 25, 2015

### toothpaste666

or should I find an exact reccurence relation and prove it is less than the one they give me?

7. Mar 25, 2015

### OlderOwl

I say the latter route, Solve moving 2 disks, 4 disks, 6 disks, 8 disks and note the algorithm that solves the problem in the fewest moves each time to see the relation of that series. Then solve for moving 1 disk, 3 disks, 5 disks, 7 disks etc and note that relation. In the end the relations may or may not be favorable to a proof by induction.

8. Mar 25, 2015

### haruspex

Not sure what distinction you're making. Yes, you need to use induction, but it's a matter of finding a recursive algorithm, not of playing with the algebra. It will give you an exact recurrence relation for your algorithm. It won't prove that your algorithm is the best, but it will prove the inequality required.
Do you know the recursive algorithm for the three pole case? What you need here is a very simple extension of it.

9. Mar 26, 2015

### toothpaste666

I know the 3 pole case is
$s_k = 2s_{k-1} +1$
but the derivation of this in the book was confusing to me

10. Mar 26, 2015

### toothpaste666

I think I get where the induction comes in. I must find a recurrence relation for the 4 pole case and then use induction to prove it is always less than or equal to the inequality they give me.

11. Mar 26, 2015

### toothpaste666

I am confused. It seems to me that
$s_k = 2s_{k-2} +3$
can I say that because it is = to that for all k then it is also <= ?

12. Mar 26, 2015

### toothpaste666

I am sorry guys. I was horribly confused which made me describe the problem incorrectly. In this question sk is the MINIMUM number of moves. I know that it can be done in
$2s_{k-2} + 3$
moves for all k>=3. Then it follows that the minimum number of moves it can be done in is either that or less than that. Is this an adequate proof?

13. Mar 26, 2015

### haruspex

Yes, I understood it was defined to be the minimum.
And yes, if you can show that if k-2 can be moved in n steps then k can be moved in 2n+3 steps it follows that k can be moved in $2s_{k-2} + 3$ steps, and thence that $s_k <= 2s_{k-2} + 3$.

14. Mar 26, 2015

### OlderOwl

I think the recusive algorithm is based on the fact that it takes Sk-2 steps to move k-2 discs to one pole then you have 2 free poles to move the remaining 2 discs. But you also have to prove that this is the minumum possible number of moves i.e. that Sk >= 2*(Sk-2) + 3 !!!

Last edited: Mar 26, 2015
15. Mar 26, 2015

### haruspex

I presumed from post #12 that toothpaste already figured that out.
The question does not require that. The algorithm shows that moving k can be done in 2*(Sk-2) + 3 moves, where Sk-2 is defined to be the minimum number required for k-2 discs. Note that we do not know and do not care what Sk-2 is numerically. It follows that Sk <= 2*Sk-2+3.