Let a sequence $X_0, X_1, X_2, . . .$ be defined in the following way: \begin{equation*} X_0 = 1 \end{equation*} \begin{equation*} X_1 = 2 \end{equation*} \begin{equation*} X_n = 3X_{n−1} + 2X_{n−2}. \end{equation*}
Prove that $\forall n \geq 0 : X_n \leq 4^n$. What are the base cases? What is the inductive step?
I made it as far as getting the following inequality in my inductive step but I can't proceed any further.
\begin{equation*} 11X_{n-1}+2X_{n-2}\leq4^{n+1} \end{equation*}
HINT
with inductive assumption, you have $$ \begin{split} X_n &= 3X_{n-1} + 2X_{n-2} \\ &\le 3\cdot 4^{n-1} + 2 \cdot 4^{n-2} \\ &= 3\cdot 4^{n-1} + \frac{1}{2}\cdot 4^{n-1} \\ &= 4^n - 0.5\cdot 4^{n-1} \end{split} $$ Can you finish this?