# Thread: Inductive Proof, is this way valid?

1. ## 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.

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 $\displaystyle n\geq4$ and $\displaystyle 2^n \geq n^2$ is true.

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

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

Now,

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

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

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

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

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

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

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

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

Consequently, $\displaystyle 2^n\geq n^2$ is true for all $\displaystyle n \geq 4$

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.

4. 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

5. 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.

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