If $a_0=1$， $a_1=3$, $a_2=9$ and $a_{n+3}=a_{n+2}+4a_{n+1}+5a_n$, show $a_n\le 3^n$.
I don't know how to type it in right format. $n+3$ and such things in the parentheses are small and in the lower right corner.
I think this question relates to recursion and induction, but I cannot solve it.
On
This is strong induction.
The case for $a_0$ and $a_1$ and $a_2$ are givens.
Suppose true for all $a_n$ $n \le k$ for some k.
Then $a_{k+1} = a_k + 4a_{k-1} + 5a_{k-2} \le 3^k + 4*3^{k-1} + 5*3^{k-2}$
$= 3^k + (3 + 1)*3^{k_1} + (3 + 2)3^{k-2} = $
$3^k + 3^k + 3^{k-1} + 3^{k-1} + 2*3^{k-2} =$
$2*3^k + 2*3^{k-1} + 2*3^{k-2} = $
$2*3^k + (3 - 1)3^{k-1} + (3-1)3^{k-2}= $
$2*3^k + 3^k -3^{k-1} + 3^{k-1} - 3^{k-2} =$
$3^k - 3^{k-2} < 3^k$.
This looks suitable for induction.
First you have to prove a base case, in this it would be for $n=0$, and the statement to prove is $a_0\leq 3^0$. That's shouldn't be a problem.
Then you have to do the inductive step, i.e. prove that if $a_k\leq 3^k$ for $k\leq n$ then $a_{n+1}\leq 3^{n+1}$.
If we rewrite the recursive defintion, to get $a_{n+1}$, we get: $$ a_{n+1}=a_n+4a_{n-1}+5a_{n-2} $$ If you use the inductive hypothesis you get
At this point you have to use that $5+3<9$, but then it follows quite simply.