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.

  • 1
    $\begingroup$ Hit: $3^n+3^n+3^n = 3^{n+1}$ $\endgroup$
    – JavaMan
    Oct 12 '18 at 4:09
  • $\begingroup$ @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? $\endgroup$ Oct 12 '18 at 4:26

If $h_k\lt3^k$ then:


...or, in short:

$$ h_{k+1}<3^{k+1}$$

...which completes the induction step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.