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


$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?

  • $\begingroup$ "because $2a_{k-2}+3a_{k-3}$ is always smaller than $3a_{k-2}$". You haven't proven that yet. Separate it as a lemma/subproblem and prove it. It looks like in your mind you see it as also a statement that follows from induction. So, make it explicit. In particular, its base case. $\endgroup$
    – plop
    Commented Sep 3, 2020 at 23:29
  • $\begingroup$ once I've proven that, is my proof considered valid? @plop $\endgroup$ Commented Sep 4, 2020 at 0:14
  • $\begingroup$ Yes, I think so. $\endgroup$
    – plop
    Commented Sep 4, 2020 at 0:21
  • $\begingroup$ It keeps on recursing. The same problem as in the original one.I'm not sure how to deal with the recurrence part of the proof. $\endgroup$ Commented Sep 4, 2020 at 0:37
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Sep 4, 2020 at 2:02

1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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