If $a(n)$ is defined by: $$a(0)=1 \quad a(1)=3\quad a(2)=9 $$ and, for $n≥3$: $$a(n)=a(n-1)+2a(n-2)+5a(n-3)$$
show: $a(n) ≤ 3^n$
So I know that I'll have to use either Induction or Strong Induction to prove this statement. I'd begin by proving the base case for $3$, but I am not sure if Strong induction would apply better. I'm having trouble showing that the inequality holds. I obtained a formula that for $a(k)$ and $a(k+1)$ but it is not in in closed form. Would that help?
$$a(k+1)=98+7(a(3)+a(4)+...+a(k-2))+2a(k-1)$$
I'll try deriving a closed form for the recursion.