Solving inequality with a recursive formula without its closed form?

Question

I have the following problem: $$a_{1}=1$$ $$a_{2}=3$$ $$a_{n+2}=a_{n+1}+5a_{n}$$ I have to prove this inequality: $$a_{n}<1+3^{n-1}$$ So my question, is there a way to solve this inequality without having the explicit formula for $a_{n}$ ? We are using induction in my course, but there was no further explanation on how to find explicit formulas (though I'm not asking for that exactly). Thanks!

Answer 1

Induction, perhaps. For $\;n=1,2\;$ it is trivial, so suppose it is true for all $\;k<n+2\;$ and let us try to prove for $\;k=n+2\;,\;\; n\ge3\;$ :

$$a_{n+2}=a_{n+1}+5a_n\stackrel{\text{Ind. Hyp.}}<1+3^n+5+5\cdot3^{n-1}=6+8\cdot3^{n-1}$$

Now, we'd like to show

$$6+8\cdot3^{n-1}\le1+3^{n+1}\iff1+3^{n-1}(9-8)\ge6$$

and it's easy to check the last inequality is true, so we've finished.

Answer 2

Iduction should work well: Assume we already know that $a_n<1+3^{n-1}$ and $a_{n+1}<1+3^n$. Then $$ \begin{align}a_{n+2}&=a_{n+1}+5a_n\\&<1+3^n+5\cdot(1+3^{n-1})\\&=6+8\cdot 3^{n-1}\\&=6+3^{n-1}-3^{n-1}\\ &<1+3^{n+1}\end{align}$$ provided that $3^{n-1}>5$. This last requirement holds as soon as $n\ge 3$, so you need to show the inequality "by hand" for $a_1,\ldots, a_4$.