# Thread: My other induction question (sequences)

1. ## My other induction question (sequences)

I am trying to figure this out.
I have used . to denote subscript.

A sequence h.0,h.1,h.2,... is defined as h.0=1, h.1=2, h.2=3
h.k= h.k-1 + h.k-2 + h.k-3

show h.n <= 3^n

I have it to the point where h.k+1 = h.k + h.k-1 + h.k-2
= 3^k + h.k-1 + h.k-2

but once again am stuck as to what to do.
Any help muchly appreciated

2. Originally Posted by R.Laramee
I am trying to figure this out.
I have used . to denote subscript.

A sequence h.0,h.1,h.2,... is defined as h.0=1, h.1=2, h.2=3
h.k= h.k-1 + h.k-2 + h.k-3

show h.n <= 3^n

I have it to the point where h.k+1 = h.k + h.k-1 + h.k-2
= 3^k + h.k-1 + h.k-2

but once again am stuck as to what to do.
Any help muchly appreciated
Check the base case, then assume the for some $k$, $h_k<3^k$, then:

$
h_{k+1}=h_k+h_{k-1}+h_{k-2}
$

but the sequence $h_n$ is increasing so if $h_k<3^k$, then also $h_{k-1}<3^k$ and $h_{k-2}<3^k$. hence:

$
h_{k+1}=h_k+h_{k-1}+h_{k-2}<3 \times 3^k = 3^{k+1}
$

which proves the induction step, and I can leave the rest to you.

RonL