simple proof help (I think I'm really close)

**horan** · February 25th 2009, 09:11 PM

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

What I have so far is:

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

inductive step:
assume true for the base case, then $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 $\leq 3^n$ , we really just want to show that our inductive case is $\leq 3^{n+1} = 3 \times 3^n$

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

any help with this would be greatly appreciated!

**arpitagarwal82** · February 25th 2009, 10:07 PM

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 $S_n$ is a statement that $h_n\leq 3^n$

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

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

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

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

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

**CaptainBlack** · February 25th 2009, 11:35 PM

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 $S_n$ is a statement that $h_n\leq 3^n$

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

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

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

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

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

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

CB

**arpitagarwal82** · February 26th 2009, 04:29 AM

Originally Posted by CaptainBlack

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

CB

But n this problem, you cannot just assume $S_n$ to be correct for any general integer k and prove that $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.

**CaptainBlack** · February 26th 2009, 07:25 AM

Originally Posted by arpitagarwal82

But n this problem, you cannot just assume $S_n$ to be correct for any general integer k and prove that $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 $h_n<3^n$ for all integers less than or equal to $k$ , so it will be true for $k, k-1$ and $k-2$ , which is sufficient to prove it true for $k+1$ , and so for all integers less than or equal to $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

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

LinkBack

Thread Tools

Display

simple proof help (I think I'm really close)

Similar Math Help Forum Discussions

How close?

Is My Answer Close to Right? Cyclic Group Proof

Definite Integral close??

Formal Modulus Proof: How close am I?

Compact and Close Set

Search Tags