Show that the inequality holds for all positive integers

Question

$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n>=3$

Show $a_n<3^n$ for all positive integers n

Base case: $a_3 = 2*9+3*2 = 24<=3^3$ is true

Hypothesis: $a_k<=3^k$ for $k\epsilon\mathbb{N}$, show $a_{k+1}<=3^{k+1}$

Begin:

$a_k<=3^k$ implies $3a_k<=3^{k+1}$

by definition: $a_{k+1} = 2a_k+3a_{k-1}$

$2a_k + 3a_{k-1} <= 2a_k + a_k = 3a_k <= 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} <= 3a_k$ and $3a_k<=3^{k+1}$ then $a_{k+1}<=3^{k+1}$ which proves $a_n<=3^n$ for all n

Is my proof legit?

Answer 1

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<3\cdot 9=3a_2$$

---

We also don't have $a_k<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<k$.

Then $$\begin{align} a_k&=2a_{k-1}+3a_{k-2}\\ &\leq 2\cdot 3^{k-1}+3\cdot 3^{k-2}\\ &=3\cdot 3^{k-1}\\ &=3^{k} \end{align}$$

Therefore, $a_{k}\leq 3^{k}$.

By induction, for all natural $k$ we have that $a_{k}\leq 3^k$.