Proof by Induction help (inequality)

Question

I need to prove if, $$a_1=1,\ a_2=2$$ and $$a_n=2a_{n-1}+a_{n-2}$$ then $$a_n\leq \left(\frac{5}{2} \right)^{n-1}$$

Proof (by using strong induction):

As far as I go, is that I prove both bases where $n=1$ and $n=2$, so I then know that $a_{n+1}=2a_{n}+a_{n-1}$ where I follow (by using strong induction) that

$$a_{n+1}\leq 2\left(\frac{5}{2} \right)^{n-1}+ \left(\frac{5}{2} \right)^{n-2}$$ where it's where I get stuck, what I do is that I know the second term is a positive number, so I can remove it and the inequality remains

$$a_{n+1}\leq 2\left(\frac{5}{2} \right)^{n-1}$$

then I know that $x^{n-1}=\left(\frac{x^n}{n} \right)$ so

$$a_{n+1}\leq \left(\frac{4}{5} \right)\left(\frac{5}{2} \right)^{n}$$ And that's pretty much where I'm stuck, since I don't know if I can go on from there.

Thank for any help!

Answer 1

You can't remove the second term. $$a_{n+1}\leq 2\left(\frac{5}{2} \right)^{n-1}+ \left(\frac{5}{2} \right)^{n-2}$$ $$\leq \left(\frac{5}{2} \right)^{n-2} [2\left(\frac{5}{2} \right) + 1] = 6 \left(\frac{5}{2} \right)^{n-2} \\ < \left(\frac{5}{2} \right)^2 \left(\frac{5}{2} \right)^{n-2} = \left(\frac{5}{2} \right)^n$$

This proves the induction hypothesis.

Answer 2

The base is obvious.

Now, by the assumption of the induction we obtain: $$a_n\leq2\left(\frac{5}{2}\right)^{n-2}+\left(\frac{5}{2}\right)^{n-3}.$$ Thus, it's enough to prove that $$2\left(\frac{5}{2}\right)^{n-2}+\left(\frac{5}{2}\right)^{n-3}\leq\left(\frac{5}{2}\right)^{n-1}$$ or $$2\cdot\frac{5}{2}+1\leq\left(\frac{5}{2}\right)^2.$$ Can you end it now?

Answer 3

Using the ansatz $$a_n=q^n$$ we get the following explicit solution $$a_n=-\frac{\left(2+\sqrt{2}\right) \left(\left(1-\sqrt{2}\right)^n-\left(1+\sqrt{ 2}\right)^n\right)}{4 \left(1+\sqrt{2}\right)}$$