# Induction on a sequence inequality

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*}$$

## 1 Answer

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?

• Why would you add $1$? $X_n\le 4^n$ not $4^n+1$ – Andrei Dec 18 '18 at 19:46
• @Andrei in the initial version of the question OP wanted to prove $X_n \le 4^n+1$ – gt6989b Dec 18 '18 at 19:47
• I did not notice that. Sorry. – Andrei Dec 18 '18 at 19:48