Given a series $b_0,b_1,...$, where $b_0=1,b_1 = 2,b_2 = 3$ and $b_n=b_{n-3}+b_{n-2}+b_{n-1}$, show $b_n \leq 3^n$ for $n>2$. I have a series $b_0, b_1...$, where $b_0 = 1$, $b_1 = 2$, $b_2 = 3$ and $b_n = b_{n-3} + b_{n-2}+b_{n-1}$. I have to show, that when $n > 2$ and $n \in \Bbb Z$, then $b_n \leq 3^n$. 
I'm using mathematical induction. 
Base case $n = 3$
$b_3= b_0 + b_1 + b_2 = 1 + 2 +3 = 6\\  b_3 \leq 3^3 \rightarrow 6 \leq 27$
So I presume that $b_k \leq 3^k$ is true and I should show that $b_{k+1} \leq 3^{k+1}$ is also true, but this is where I get stuck and don't know how to do it. 
How should I show this?
 A: If you stick with weak induction, your inductive hypothesis should be$$b_{3n}\le3^{3n}\land b_{3n+1}\le3^{3n+1}\land b_{3n+2}\le3^{3n+2},$$which is true if $n=0$. So you just need to show$$b_{3k}\le3^{3k}\land b_{3k+1}\le3^{3k+1}\land b_{3k+2}\le3^{3k+2}\implies b_{3k+3}\le3^{3k+3}\land b_{3k+4}\le3^{3k+4}\land b_{3k+5}\le3^{3k+5}.$$
A: Take $b_{k+1}$ with the assumption that the claim holds for all $b_j$ when $j\le k$. Now, by definition, $b_{k+1}=b_k+b_{k-1}+b_{k-2}$. The induction hypothesis tells us that $b_n\le 3^n$ for $n\le k$, so $b_{k+1} \le 3^k+3^{k-1}+3^{k-2}<3^k+3^k+3^k=3\cdot3^k=3^{k+1}$.
A: You have to assume it is true
for the 3 previous cases.
If $b_k \le 3^k$
for $k = n-1, n-2, n-3$
then
$\begin{array}\\
b_n
&=b_{n-1}+b_{n-2}+b_{n-3}\\
&\le 3^{n-1}+3^{n-2}+3^{n-3}\\
&=3^n(3^{-1}+3^{-2}+3^{-3})\\
&=3^n\dfrac{9+3+1}{27}\\
&=3^n\dfrac{13}{27}\\
&\lt 3^n\\
\end{array}
$
A: You have to use a strong induction which assumes the assertion for all $k=3,\ldots,n$. Then estimate $b_{n+1}$.
This variant is necessary, because you have a recursion over three predecessors and you must know something about all of them. 
