Can a recurrence relation be proven using induction?

[toothpaste666]

Homework Statement

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

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 &lt;= 2s_{k-2}+3
and must prove that
s_{k+1} &lt;= 2s_{k-1}+3
if i call m = k+1
then k-1 = m-2 and we have
s_m &lt;= 2s_{m-2}+3
I am kinda confused though and I don't know if that proves something I didnt already know

 

[haruspex]

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

 

[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

 

[haruspex]

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

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

 

[toothpaste666]

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

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

 

[toothpaste666]

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

 

[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.

 

[haruspex]

should I use induction or was i heading in the wrong direction?
or should I find an exact reccurence relation and prove it is less than the one they give me?

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.

 

[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

 

[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.

 

[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 <= ?

 

[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?

 

[haruspex]

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?

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 &lt;= 2s_{k-2} + 3.

 

[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 !

 

[haruspex]

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.

I presumed from post #12 that toothpaste already figured that out.

But you also have to prove that this is the minumum possible number of moves i.e. that Sk >= 2*(Sk-2) + 3 !

The question does not require that. The algorithm shows that moving k can be done in 2*(S_k-2) + 3 moves, where S_k-2 is defined to be the minimum number required for k-2 discs. Note that we do not know and do not care what S_k-2 is numerically. It follows that S_k <= 2*S_k-2+3.