# Proof Using Strong Induction

• April 23rd 2009, 09:10 AM
tshare1
Proof Using Strong Induction
I can't figure out this problem. Any help is appreciated.

Suppose h0, h1, h2,..... is a sequence defined as follows:

h0 = 1, h1 = 2, h2 = 3

hk = hk-1 + hk-2 + hk-3 for all ints k is greater than or equal to 3.

Prove that hn is less than or equal to 3^(n).

Thank you!
• April 23rd 2009, 10:26 AM
putnam120
For $n=0,1,2$ you have that $h_n\le 3^n$. So assume the assertion is true for some $n\ge{2}$, then $h_{n+1}=h_n+h_{n-1}+h_{n-2}\le 3^n+3^{n-1}+3^{n-2}<3\cdot 3^n=3^{n+1}$.