Inductive Proof, is this way valid?

Printable View

October 8th 2009, 10:43 AM
HeadOnAPike

Inductive Proof, is this way valid?

Have to prove 2^n >= n^2 for n>=4

I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

...2(n+1)^2 >= (n+2)^2

2n^2 + 4n + 2 >= n^2 + 2n + 4
n^2 + 4n + 2 >= 2n + 4
n^2 + 2n + 2 >= 4

Since we know n must be >= 4 ...16 + 8 + 2 >= 4

So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

Is this valid? Thanks.
October 8th 2009, 01:02 PM
novice

Quote:

Originally Posted by HeadOnAPike

Have to prove 2^n >= n^2 for n>=4

I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

...2(n+1)^2 >= (n+2)^2

2n^2 + 4n + 2 >= n^2 + 2n + 4
n^2 + 4n + 2 >= 2n + 4
n^2 + 2n + 2 >= 4

Since we know n must be >= 4 ...16 + 8 + 2 >= 4

So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

Is this valid? Thanks.

Suppose $n\geq4$ and $2^n \geq n^2$ is true.

Let $n=k+3$ where $1 \leq k \leq N$

For $k=1, 2^n=16 \geq n^2=16$

Now,

If $n=k+3$ , where $2 \leq k \leq N$ , and $2^n \geq n^2$ is true.

Then when $n=3+(k+1)$

$2^{k+1} \geq (k+1)^2 \rightarrow$

$2^{k+1} \geq k^2+2k+1 \rightarrow$

$2\cdot 2^{k} \geq k^2+2k+1 \rightarrow$

Since ( $2\cdot 2^{k}$ ) $\geq 2k^2 \geq k^2+2k+1$ , then

( $2\cdot 2^{k}$ ) $\geq k^2 \geq 2k+1$

$2^{k+1} \geq (k+1)^2$ is true

Consequently, $2^n\geq n^2$ is true for all $n \geq 4$
October 9th 2009, 11:03 AM
novice

Quote:

Originally Posted by HeadOnAPike

Have to prove 2^n >= n^2 for n>=4

I.H.: Works when I plug in four. Show that 2^(n+1) >= (n+1)^2 or show that 2^n * 2 >= (n+1)^2

Since we know 2^n >= n^2 then 2^n * 2 >= 2n^2

So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

...2(n+1)^2 >= (n+2)^2

2n^2 + 4n + 2 >= n^2 + 2n + 4
n^2 + 4n + 2 >= 2n + 4
n^2 + 2n + 2 >= 4

Since we know n must be >= 4 ...16 + 8 + 2 >= 4

So we add to what we know... 2^n >= 2n^2 >= (n+1)^2 therefore 2^n >= (n+1)^2.

Is this valid? Thanks.

This part of your argument makes no sense:

So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

...2(n+1)^2 >= (n+2)^2

2n^2 + 4n + 2 >= n^2 + 2n + 4
n^2 + 4n + 2 >= 2n + 4
n^2 + 2n + 2 >= 4

Since we know n must be >= 4 ...16 + 8 + 2 >= 4

----------
In prove by induction, you cannot simply plug in numbers.
October 9th 2009, 02:31 PM
tonio

Quote:

Originally Posted by novice

This part of your argument makes no sense:

So I then go about showing through another induction proof that 2n^2 >= (n+1)^2

...2(n+1)^2 >= (n+2)^2

2n^2 + 4n + 2 >= n^2 + 2n + 4
n^2 + 4n + 2 >= 2n + 4
n^2 + 2n + 2 >= 4

Since we know n must be >= 4 ...16 + 8 + 2 >= 4

----------
In prove by induction, you cannot simply plug in numbers.

I think he meant: 2(n+1)^2 >= (n+2)^2 <==> ...etc., until he arrived to
...<==> n^2 + 2n + 2 >= 4, and since this last inequality is obviously true whenever n >= 4 then we can go backwards and get what we wanted.

Tonio
October 9th 2009, 02:37 PM
novice

Quote:

Originally Posted by tonio

I think he meant: 2(n+1)^2 >= (n+2)^2 <==> ...etc., until he arrived to
...<==> n^2 + 2n + 2 >= 4, and since this last inequality is obviously true whenever n >= 4 then we can go backwards and get what we wanted.

Tonio

Thank you, Tonio.
October 9th 2009, 02:39 PM
HeadOnAPike

Sorry for the ambiguity there. So I am assuming this is good?
October 9th 2009, 04:46 PM
novice

Quote:

Originally Posted by HeadOnAPike

Sorry for the ambiguity there. So I am assuming this is good?

Yes, it is a valid argument. It will be superb if you could make your arguments flow.