Suppose $h_0, h_1, h_2, \dots$ is a sequence defined:
$\qquad h_0=1, h_1=2, h_2=3$
$\qquad h_k=h_{k-1}+h_{k-2}+h_{k-3}, \forall k \in \mathbb{Z}\wedge k\ge 3$
Prove that $h_n \le 3^n,\forall n \in \mathbb{Z} \wedge n \ge 0$.
My basis is:
$(h_0 = 1) \le 3^0$ is true.
$(h_1 = 2) \le 3^1$ is true.
$(h_2 = 3) \le 3^2$ is true.
$(h_3 = 6) \le 3^3$ is true.
My inductive hypothesis is:
$h_k \le 3^k$ is true, for $3 \le k < n, n \in \mathbb{Z}$
$h_{k-1} + h_{k-2} + h_{k-3} \le 3^n$
Looking at the $k+1^{th}$ term, I have:
$h_{k+1} = h_{k} + h_{k-1} + h_{k-2}$
I'm really unsure where to go from here to prove the $k+1$ term is less than or equal to $3^n$. I can expand the $h_k$ term to get $2 * h_{k-1} + 2 * h_{k-2} + h_{k-3}$, but that doesn't seem to get me anywhere.
If $h_k\lt3^k$ then:
$$h_{k+1}=h_{k}+h_{k-1}+h_{k-2}<3^{k}+3^{k-1}+3^{k-2}<3^{k}+3^{k}+3^{k}=3^{k+1}$$
...or, in short:
$$ h_{k+1}<3^{k+1}$$
...which completes the induction step.