# Show that the inequality holds for all positive integers

$$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$$ for $$n>=3$$

## Hypothesis: $$a_k<=3^k$$ for $$k\epsilon\mathbb{N}$$, show $$a_{k+1}<=3^{k+1}$$

Begin:

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

• "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.
– plop
Commented Sep 3, 2020 at 23:29
• once I've proven that, is my proof considered valid? @plop Commented Sep 4, 2020 at 0:14
• Yes, I think so.
– plop
Commented Sep 4, 2020 at 0:21
• 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. Commented Sep 4, 2020 at 0:37
• 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.
– D.W.
Commented Sep 4, 2020 at 2:02

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.

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