- #1
toothpaste666
- 516
- 20
Homework Statement
prove that
[itex] s_k <= 2s_{k-2}+3 [/itex]
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
[itex] s_3 <= 2s_1 + 3 [/itex]
5 <= 2+3
that is true. Now i must prove the inductive step. This is where I am having trouble.
I assume that [itex] s_k <= 2s_{k-2}+3 [/itex]
and must prove that
[itex] s_{k+1} <= 2s_{k-1}+3 [/itex]
if i call m = k+1
then k-1 = m-2 and we have
[itex] s_m <= 2s_{m-2}+3 [/itex]
I am kinda confused though and I don't know if that proves something I didnt already know