prove $S(n) \leq (5/2)^n$

Question

I've been flipping through my math book for nearly 5 hours working on these recursive problems and it's just not clicking.

I have a recusrive sequence

$S(0) =1$

$S(1)=2$

$S(n) = 2S(n-1) +S(n-2)$ for $n \geq 2$

I need to prove $S(n)$ $\leq$ $(5/2)^n$ for $n \geq 0$

I get to this step: $2S(n) + S(n-1) \leq ((5/2)^2) (5/2)$ but at this step I"m not sure what to do. I know I need to use my induction hypothesis but I don't see how.

Answer 1

$1 \le (5/2)^0$ and $2 \le (5/2)^1$. Now apply the induction step. If $s_{n-2} \le (5/2)^{n-2}$ and $s_{n-1} \le (5/2)^{n-1}$ then $$s_n \le 2 \left( \frac 52 \right)^{n-1} + \left(\frac 52 \right)^{n-2} = \left(\frac 52 \right)^{n-2} (5 + 1) < \left(\frac 52 \right)^{n-2} \frac{25}{4} = \left(\frac 52 \right)^n.$$

Answer 2

To Prove: $$S(n) \le (5/2)^n$$

By definition: $$2S(n - 1) + S(n-2) \le (5/2)^n$$

Rewrite, need to prove: $$S(n-1) \le \frac{(5/2)^n - S(n-2)}{2}$$

To prove $a \le b$, if you can assume $a \le c$, then it suffices to prove $c \le b$. By induction we can assume $S(n-1) \le (5/2)^{n-1}$. So:

$$(5/2)^{n-1} \le \frac{(5/2)^n - S(n-2)}{2}$$

Rewrite:

$$2(5/2)^{n-1} + S(n-2) \le (5/2)^{n}$$

Similarly for $S(n-2)$ :

$$2(5/2)^{n-1} + (5/2)^{n-2} \le (5/2)^{n}$$

Multiply through by $(5/2)^{-n}$:

$$2(5/2)^{-1} + (5/2)^{-2} \le 1$$

Multiply through by $5^2$:

$$2\cdot 5 \cdot 2 + 2^2 \le 5^2$$ $$24 < 25$$ $$\top$$