Prove by induction $a_n \le3.8^n$ for all $ n \ge2$

Question

Original Question. Part 1Original Question. Part 2.Hi i just have a quick question. I have a question for my assignment which asks for a(n). I believe I have solved for a(n) and it is $$ a_n = 7a_{n-2} + 14a_{n-3}$$ (the question asks specifically to solve it in terms of n-2 and n-3)

so I have that statement and now it is asking me to prove by induction that a(n)<=3.8^n for all n=>2.

I figured the basic induction step but I can't seem to find how to expand it or substitute a(k) into a(k+1) statement during the induction step.

sorry I should have mentioned that a(1) = 7, a(2) = 14, a(3) = 49, a(4) = 196 for n=>4. and a(0) = 0

Answer 1

What is the value of $a_0,a_1,a_2$? It is unlikely that $a_n \le 3.8^n$ since usually $a_n = O(4.497324135953^n)$ since the real root of characteristic equation $x^3-14x-28$ is 4.497324135953

Answer 2

Assume the result for both $a_k$ and $a_{k+1}$.

Then $a_{k+3}$ is no greater than $7.3.8^{k+1}+14.3.8^{k}$. This sum is less than $3.8^{k+3}$, as required.

Answer 3

For the induction step, we need to show

$$a_{n+1} = 7a_{n-1} + 14a_{n-2} \le 3.8^{n+1}$$

Let $\alpha = 3.8$. Then, provided that

$$ a_{n-2} = 7a_{n-4} + 14a_{n-5}\le \alpha^{n-2}$$ $$ a_{n-1} = 7a_{n-3} + 14a_{n-4}\le \alpha^{n-1}$$ $$ a_n = 7a_{n-2} + 14a_{n-3}\le \alpha^n$$

we could complete the induction step by

$$a_{n+1} = 7a_{n-1} + 14a_{n-2}\le 7(\alpha^{n-1})+14(\alpha^{n-2})=\Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\alpha^n$$

which would imply that

\begin{align}\Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\le \alpha &\implies 7\alpha+14\leq \alpha^3 \\&\implies\alpha^3-7\alpha-14\ge 0\\&\implies \alpha\ge\frac{1}{3}\sqrt[3]{189-42\sqrt{15}}+\frac{\sqrt[3]{7\big(9+2\sqrt{15}}\big)}{3^{2/3}}\\&\implies \alpha \ge 3.34454 \end{align}

therefore as we are given that $\alpha=3.8$ it follows that

$$a_{n+1} = \Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\alpha^n \leq 3.8^{n+1}$$