# Thread: simple proof help (I think I'm really close)

1. ## simple proof help (I think I'm really close)

Suppose that $\displaystyle h_0, h_1, h_2, h_3, \dots$ is a sequence defined as follows: $\displaystyle h_0 = 1, h_1 = 2, h_2 = 3, h_k = h_{k-1}+h_{k-2}+h_{k-3}$ for all ints $\displaystyle k \geq 3$. Prove that $\displaystyle h_n\leq 3^n$ for all ints $\displaystyle n \geq 0$

What I have so far is:

base case n=0, then $\displaystyle h_0=1$ and $\displaystyle 1 \leq 3$.

inductive step:
assume true for the base case, then $\displaystyle h_{n+1} = h_{(n+1)-1} + h_{(n+1)-2} + h_{(n+1)-3} = h_{n} + h_{n-1} + h_{n-2}$

since the base case is $\displaystyle \leq 3^n$, we really just want to show that our inductive case is $\displaystyle \leq 3^{n+1} = 3 \times 3^n$

but how can I show that $\displaystyle h_{n+1} \leq 3^{n+1}$?

any help with this would be greatly appreciated!

2. We will use Mathematical induction to proove this. But here you dont just have to asume that its true for k and prove for k+1. Here we have to use the extended case of MI.

Assume $\displaystyle S_n$ is a statement that $\displaystyle h_n\leq 3^n$

Now show that $\displaystyle S_0$, $\displaystyle S_1$ and $\displaystyle S_2$ is correct. (which infact is)

Now assume
$\displaystyle S_{k-1}$, $\displaystyle S_{k-2}$ and $\displaystyle S_{k-3}$ are true.
i.e.
$\displaystyle h_{k-1} \leq 3^{k-1}$
$\displaystyle h_{k-2}\leq 3^{k-2}$
$\displaystyle h_{k-3}\leq 3^{k-3}$

Now prove that $\displaystyle S_k$is trure.
To proove
$\displaystyle h_k \leq 3^k$

now $\displaystyle h_k = h_{k-1}+h_{k-2}+h_{k-3}$
$\displaystyle => h_k \leq 3^{k-1} + 3^{k-2} + 3^{k-3}$

Now in a few step you can show that $\displaystyle S_k$ is true. hence proved.

3. Originally Posted by arpitagarwal82
We will use Mathematical induction to proove this. But here you dont just have to asume that its true for k and prove for k+1. Here we have to use the extended case of MI.

Assume $\displaystyle S_n$ is a statement that $\displaystyle h_n\leq 3^n$

Now show that $\displaystyle S_0$, $\displaystyle S_1$ and $\displaystyle S_2$ is correct. (which infact is)

Now assume
$\displaystyle S_{k-1}$, $\displaystyle S_{k-2}$ and $\displaystyle S_{k-3}$ are true.
i.e.
$\displaystyle h_{k-1} \leq 3^{k-1}$
$\displaystyle h_{k-2}\leq 3^{k-2}$
$\displaystyle h_{k-3}\leq 3^{k-3}$

Now prove that $\displaystyle S_k$is trure.
To proove
$\displaystyle h_k \leq 3^k$

now $\displaystyle h_k = h_{k-1}+h_{k-2}+h_{k-3}$
$\displaystyle => h_k \leq 3^{k-1} + 3^{k-2} + 3^{k-3}$

Now in a few step you can show that $\displaystyle S_k$ is true. hence proved.
There is no need to use the extended version of MI. Just make $\displaystyle S_n$ the statement: $\displaystyle h_k<3^k$ for all $\displaystyle k: 0 \le k\le n$. Then the base case is $\displaystyle S_2$, and so on.

CB

4. Originally Posted by CaptainBlack
There is no need to use the extended version of MI. Just make $\displaystyle S_n$ the statement: $\displaystyle h_k<3^k$ for all $\displaystyle k: 0 \le k\le n$. Then the base case is $\displaystyle S_2$, and so on.

CB
But n this problem, you cannot just assume $\displaystyle S_n$to be correct for any general integer k and prove that $\displaystyle S_{k+1}$ is true. It would be impossible.

You have to assume that statement is true fr three cnsicutive integers ( I took k-3, k-2, k-1) and show that statement is true for fourth consecutive integer (k in my case).

Also you have to show that statement is true for first three integers.

5. Originally Posted by arpitagarwal82
But n this problem, you cannot just assume $\displaystyle S_n$to be correct for any general integer k and prove that $\displaystyle S_{k+1}$ is true. It would be impossible.

You have to assume that statement is true fr three cnsicutive integers ( I took k-3, k-2, k-1) and show that statement is true for fourth consecutive integer (k in my case).
Here we would be assuming it true that $\displaystyle h_n<3^n$ for all integers less than or equal to $\displaystyle k$, so it will be true for $\displaystyle k, k-1$ and $\displaystyle k-2$, which is sufficient to prove it true for $\displaystyle k+1$, and so for all integers less than or equal to $\displaystyle k+1$. Which is exactly what you do with extented induction, indeed the principle of extended induction is provable from standard mathematical induction by a very similar method.

Also you have to show that statement is true for first three integers.
I say "Then the base case is .." My is exactly this and is proven exactly as in your proof.

What I propose is in essense exactly the same as the other proof. It uses standard MI rather than EMI by changing the form of the stament that we are going to prove by induction, but the substance is identical.

CB