Inductions and proofs

Question

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?

$2^{n-1} + 2^{n-2} + 2^{n-3} = 2^{n-3}(4 + 2 + 1) \leq 2^{n-3}2^3$ — M.B., Apr 07 '14 at 06:35
Please confirm that my LaTeX markup reflects your question, particularly if h_n -2 was correctly interpreted as $h_{n-2}$ ( $h_{n-2}$ ). — AlexR, Apr 07 '14 at 06:45

score 1 · Answer 1 · answered Apr 07 '14 at 06:34

1

Straightforward induction, using $2^{n-1}+2^{n-2}+2^{n-3}=2^n\cdot\left (\frac12+\frac14+\frac18\right)$.

answered Apr 07 '14 at 06:34

Hagen von Eitzen

374,180

score 0 · Answer 2 · answered Apr 07 '14 at 06:36

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.

Inductions and proofs

2 Answers2