Proving 2^n > n^2 for n >= 4 by Induction

[ayusuf]

I have to prove by induction that for n>= 4 that 2^n > n^2.

So i start with the base case and I get 16 >= 16 which is true.
Then I assume for k that 2^k >= k^2 for k.
Now I have to that 2^(k+1) >= (k+1)^2

Now going back to 2^k >= k^2 if I multiply both sides by 2 I get
2*2^k >= 2*k^2
2^(k+1) >= 2*k^2

and from here I get stuck. Any help would be appreciated. Thanks.

 

[CRGreathouse]

4k^2 >= 2k^2

 

[ayusuf]

I'm sorry but I don't know what you mean by that.

 

[radou]

It works for the basis of induction, n = 4. Assume it works for some k, so 2^k >= k^2. Then, for k+1, you have 2^(k+1) = 2*2^k >= 2*k^2. Now, can you show that 2*k^2 >= (k+1)^2, for n >= 4?

 

[ayusuf]

Okay I see why you do that so I guess I have to prove 2*k^2 >= (k+1)^2 by induction.

When n = 4 we have
2*(4)^2 = 32
(4+1)^2 = 25
So 32 > 25 which is true.

Then we assume it is true for all n right and now I have to show that
2*(k+1)^2 >= ((k+1)+1)^2
which is the same thing as
2*(k+1)^2 >= (k+2)^2

Okay now I'm stuck again.

 

[Mentallic]

So you're trying to prove 2k^2\geq (k+1)^2 for k \geq 4
Expanding gives: 2k^2\geq k^2+2k+1
and now collecting like terms: k^2-2k-1\geq 0

Can you finish this off?

 

[ayusuf]

No not really. I'm not even sure I'm going the right way because my professor was telling me that I will eventually have to prove another property which is n^2 >= 2n+1 for n>=3. Thanks.

 

[Mentallic]

That's exactly where you're heading!

I just asked you to prove k^2-2k-1\geq 0 for k\geq 4 which is basically the same as what your professor said you'll have to do.

Make the above inequality a perfect square.

 

[ayusuf]

Okay so from k^2 - 2k - 1 >= 0 for k>= 4 we can rewrite it as

(k-1)^2 >= 0 for k>= 4. Yes I'm sorry but I still don't see it.

 

[Mentallic]

No that's not exactly right.
(k-1)^2=k^2-2k+1 and you have k^2-2k-1

What you're actually looking for is (k-1)^2-2\geq 0. So, for what positive k is (k-1)^2\geq 2 ?

 

[ayusuf]

It is 3 because (3-1)^2 >= 2 because 2^2 >= 2 which is 4 >= 2 but what does that prove then?

 

[Mentallic]

Yes that's right.

Well if we backtrack your steps, notice that we were trying to prove 2^k\geq k^2 Our first step was to show for a base case, and while n=1 and n=2 worked, n=3 is untrue so we started at the first case of n=4.
Now in the 3rd step you've proven that 2^{k+1}\geq (k+1)^2 by assuming 2^k\geq k^2 in your 2nd step and then substituting this assumed result to obtain 2k^2\geq (k+1)^2.

That is, if 2^k\geq k^2 then 2^{k+1}\geq 2k^2 and surely if we're trying to prove 2^{k+1}\geq (k+1)^2 then we can substitute 2^{k+1}=2k^2.

Now you've shown by logic that for k\geq 3, (k-1)^2\geq 2 which, after giving a little word about how mathematical induction works, you've essentially proven the question for k\geq 4

 

[ayusuf]

Okay I kind of get. By showing that for k>=3 we know (k-1)^2 >= 2 which originally means 2k^2 >= (k+1)^2 for k>=4 but by proving the first inequality we have proved the previous inequality and thus by proving the previous inequality this means we have proved 2^k >= k^2 for k >= 4. Am I right?

 

[Mentallic]

Yes, exactly!

 

[ayusuf]

Cool, Thanks! :D