Induction on a sequence inequality

Question

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

score 1 · Answer 1 · edited Dec 18 '18 at 19:47

1

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?

edited Dec 18 '18 at 19:47

Andrei

37,370

answered Dec 18 '18 at 19:42

gt6989b

54,422

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

Induction on a sequence inequality

1 Answers1