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