Is Mathematical Induction Proven Correctly for $S_{k+1}:2^{k+1}>(k+1)^2$?

[ineedhelpnow]

$S_k>k^2$

$S_{k+1}:2^{k+1}>(k+1)^2$

$2*2^{k+1}>2(k+1)^2$

$2^{k+2}>2(k+1)^2$

Assume $x=k+1$

$\frac{2^{x+1}}{2}>x^2$

$2^{x+1}*2^{-1}>x^2$

$2^x>x^2$

right?

$2^{k+1}>(k+1)^2$

 

[soroban]

Hello, ineedhelpnow!

Your statements make no sense.

$S_k>k^2$ . What is this?

$S_{k+1}:2^{k+1}>(k+1)^2$
This is what you're supposed to prove.
You can't start with that statement.

I would guess that the problem is: .$2^n\,>\,n^2$
But note that this is true for ${\color{blue}n \ge 5}.$

 

[ineedhelpnow]

Do you mind explaining how to prove it. Like going through the WHOLE thing. This is the only problem that I can't get past.

 

[Deveno]

It's hard to explain *how* to prove these things without actually proving them, but I'll give it a go.

A. Suppose "something" (a therorem, or a statement of some kind) was true for the number 1.

B. Suppose further, that IF it was true for one natural number ($k$), then it is ALSO true for the NEXT natural number ($k+1)$.

Then, together with it being true for 1, we get a "chain reaction":

Letting $k = 1$, then the second statement (B), means it is true for $1 + 1 = 2$.

Letting $k = 2$, then we find it is true for $2 + 1 = 3$, as well.

Thus, using (A) and (B) together, we can prove it is true for any finite natural number $n$, in $n$ steps. Since it is thus true for ANY natural number, it is thus true for ALL natural numbers.

Sometimes, we have to modify this, and start "higher up the chain", with some number like $5$, or $2$, or $317$, and so we can only prove it for "bigger natural numbers than some starting one".

So let's look at the statement:

$2^n > n^2$.

When $n = 1$, we get:

$2 > 1$, which is true. However, when $n = 2$, we get:

$4 > 4$, which is FALSE.

When $n = 3$, we get:

$8 > 9$, again, this is false.

When $n = 4$, we get: $16 > 16$, which is again false.

When $n = 5$, we get: $32 > 25$, which is true.

When $n = 6$, we get: $64 > 36$, and it appears that the left-side is now growing much faster than the right.

So, provisionally, we shall try to prove:

For all natural numbers $n \geq 5$, we have $2^n > n^2$.

So our "base case" in this scenario, is $n = 5$.

Now suppose it was true that:

$k \geq 5$ AND $2^k > k^2$.

If we can prove this alone establishes: $2^{k+1} > (k+1)^2$, we're done.

Here's what we can use:

$2^k > k^2$ (we might need to use other facts that derive from $k \geq 5$, as well).

Now, it is OBVIOUS that:

$2^{k+1} = 2\cdot 2^k$.

Hence, from our assumption on $k$, we know that:

$2^{k+1} = 2\cdot 2^k > 2 \cdot k^2 = k^2 + k^2$.

If we knew that $k^2 \geq 2k + 1$, we can use the transitive property of $>$ to conclude:

$2^{k+1} > (k+1)^2$, like so:

$2^{k+1} > k^2 + k^2 \geq k^2 + 2k + 1 = (k+1)^2$.

So now the "sticking point" is: for which $k$ is it true that $k^2 \geq 2k + 1$?

(if it turns out that this is true for any $k \geq 5$, we're home-free).

This will set up the infinite proof-chain:

True for 5 $\implies$ true for 6 $\implies$ true for 7 $\implies$ true for 8 $\implies \dots$

 

[ineedhelpnow]

what i meant is if someone could prove it. :)

 

[ineedhelpnow]

i understand the idea. i just have trouble showing the steps on paper. in a way that makes sense.

 

[Deveno]

Did what I write "make sense' to you?

 

[ineedhelpnow]

yes (Dull)