Inductions and proofs Let $(h_n)$ be a sequence defined by $h_0 =1 , h_1 = 2, h_2 =3$ and $h_n = h_{n-1} + h_{n-2} + h_{n-3}$, for all $n\ge 3$. Prove that $h_n\le 2^n$ , for all $n\ge 0$
Not sure how to go with this problem?

Let's prove it by strong induction on $n$. 
Base case: $n = 0$. $h_0 = 1 = 2^0$. So assume it is true for $n < k$. We prove it is true for $n = k+1$. 
$h_{k+1} = h_k + h_{k-1} + h_{k-2} \leq 2^k + 2^{k-1} + 2^{k-2} = \dfrac{2^{k+1}}{2} + \dfrac{2^{k+1}}{4} + \dfrac{2^{k+2}}{8} = \dfrac{7}{8} \cdot 2^{k+1} < 2^{k+1}$.
So by strong induction, the statement is proven.
