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



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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.