Show that the inequality holds for all positive integers $a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n&gt;=3$
Show $a_n&lt;3^n$ for all positive integers n
Base case: $a_3 = 2*9+3*2 = 24&lt;=3^3$ is true
Hypothesis: $a_k&lt;=3^k$ for $k\epsilon\mathbb{N}$, show $a_{k+1}&lt;=3^{k+1}$
Begin:
$a_k&lt;=3^k$ implies $3a_k&lt;=3^{k+1}$
by definition: $a_{k+1} = 2a_k+3a_{k-1}$
$2a_k + 3a_{k-1} &lt;= 2a_k + a_k = 3a_k &lt;= 3^{k+1}$
Because $3a_{k-1} = 2a_{k-1} + a_{k-1} = 2a_{k-1}+2a_{k-2}+3a_{k-3}$
$3a_{k-1}$ will always be smaller than $a_k$ because $2a_{k-2}+3a_{k-3}$ is always smaller than $3a_{k-2}$
So because $a_{k+1} &lt;= 3a_k$ and $3a_k&lt;=3^{k+1}$ then $a_{k+1}&lt;=3^{k+1}$ which proves $a_n&lt;=3^n$ for all n
Is my proof legit?
We are not going to prove that $a_k\geq 3a_{k-1}$ because it is not true: $$a_3=2a_2+3a_1=2\cdot 9+3\cdot 2=24&lt;3\cdot 9=3a_2$$

We also don't have $a_k&lt;3^k$ for all $k$, since $a_2=9=3^2$. That's probably a typo.

Let's prove, by induction, that for all natural $k$ we have $a_k\leq 3^k$.
We have that $a_1=2\leq 3=3^1$.
Assume that $a_{k-2}\leq 3^{k-2}$ and $a_{k-1}\leq 3^{k-1}$. Or you can assume that $a_t\leq 3^t$ for all $t&lt;k$.
Then
$$\begin{align}
a_k&amp;=2a_{k-1}+3a_{k-2}\\
&amp;\leq 2\cdot 3^{k-1}+3\cdot 3^{k-2}\\
&amp;=3\cdot 3^{k-1}\\
&amp;=3^{k}
\end{align}$$
Therefore, $a_{k}\leq 3^{k}$.
By induction, for all natural $k$ we have that $a_{k}\leq 3^k$.