# Proving recursive inequality with strong induction

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.

• Hit: $3^n+3^n+3^n = 3^{n+1}$ Oct 12 '18 at 4:09
• @JavaMan Oh. Would it make sense to compare $h_k \le 3^n$, $h_{k-1} \le 3^n$, $h_{k-2} \le 3^n$ and to say that it's true because of the inductive hypothesis? Or is that not valid to say? Oct 12 '18 at 4:26

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}$$
$$h_{k+1}<3^{k+1}$$