Induction Proof that 2^n > n^2 for n>=5

[dtl42]

Homework Statement

Prove that 2^{x} \geq x^{2}
\forall x\geq5

Homework Equations

2^{k} \geq x^{k}

The Attempt at a Solution

I multiplied both sides by 2, then added to factor the RHS, and eventually got to the point where I just need to prove 2^{n} \geq 2n+1 by induction also.

 

[steelphantom]

For induction, you have to prove the base case. Then you assume your induction hypothesis, which in this case is 2ⁿ >= n². After that you want to prove that it is true for n + 1, i.e. that 2ⁿ⁺¹ >= (n+1)². You will use the induction hypothesis in the proof (the assumption that 2ⁿ >= n²).

 

[Dylanette]

You know that 2^{n} \geq 2n+1 for n \geq 5. Follow Steelphantoms template for an inductive proof and take it to home plate.

 

[dtl42]

How do I know that <br /> 2^{n} \geq 2n+1<br /> for
<br /> n \geq 5<br />

That's what else I need to prove by induction.

 

[HallsofIvy]

No, Dylanette's point was that you KNOW "2^k\ge 2k+1" for some k and now want to prove that 2^{k+1}\ge 2(k+1)+ 1". (I prefer to use "k" rather than "n" again just to avoid this kind of confusion.)

If 2^k\ge 2k+1, then 2^{k+1}= 2(2^k)\ge 2(2k+ 1)= 4k+ 2.
Since you want 2(k+ 1)+ 1= 2k+ 3, try rewriting that "4k": 4k+ 2= 2k+ 2+ 2k so you need to be able to say "2k\ge 1". That's pretty obvious, isn't it?

 

[Diffy]

Halls, re-read his original problem, he has to prove that 2^{k+1} \ge (k+1)^2 assuming that 2^k \ge k^2

 

[HallsofIvy]

Okay, I reread his post. What he said was "I got to the point where I just need to prove 2^n \ge 2n+ 1 by induction also".

 

[Diffy]

oops, I should take my own advice, my bad.

 

[rwx1606]

what does RHS stand for? "added to factor the RHS"

 

[Dick]

RHS=Right Hand Side (of the equation).

 

[rwx1606]

im super stuck. don't know how to get to the 2^n > 2n+1 step that the posters are talking about. I know I have to use 2^k=k^2 and also that 2^k+1 = 2(2^k).

 

[HallsofIvy]

It's not clear to me either (now, five months after the original post). I arrive at a different point to complete the proof.

You want to show that 2^x\ge x^2 for x\ge 5.

First, when x= 5, 2⁵= 32> 25= 5² so it is true for x= 5. Now, suppose 2^k\ge k^2 for some k. We need to show that it follows that 2^{k+1}\ge (k+ 1)^2. As you say, 2^{k+1}= 2(2^k)\ge 2(k^2). The proof will be complete if we can show that 2k^2\ge (k+ 1)^2, for k\ge 5. A little algebra show that is equivalent to proving that (k-1)^2\ge 2 which is certainly true for k\ge 5

 

[statdad]

Notice that as long as k \ge 5 it is true that

<br /> k^2 &gt; 2k+1<br />

(examine the parabola k^2 - 2k - 1 to see this)

The induction anchor is that 2^k \ge k^2 for some k \ge 5. Then

<br /> \begin{align*}<br /> 2^{k+1} &amp; = 2 \left(2^k\right) \ge 2\left(k^2\right)\\<br /> &amp; = 2k^2 = k^2 + k^2\\<br /> &amp; &gt; k^2 + 2k + 1 <br /> &amp; = (k+1)^2 \\<br /> 2^{k+1} \ge (k+1)^2<br /> \end{align*}<br />

 

[almonz]

hi . If possible, please explain why :

k^2 > 2k +1

I don't understand it .

 

[HallsofIvy]

As statdad said, look at y= k^2- 2k- 1= k^2- 2k+ 1- 2= (k+1)^2-2. The graph of that is a parabola with vertex at (-1, -2). For x> -1 y is increasing and when x= 2, y= (5-1)^2- 2= 14&gt; 0. So for k> 5, k^2- 2k- 1&gt; 0 and thus k^2&gt; 2k+ 1.

 

[almonz]

As statdad said, look at y= k^2- 2k- 1= k^2- 2k+ 1- 2= (k+1)^2-2. The graph of that is a parabola with vertex at (-1, -2). For x> -1 y is increasing and when x= 2, y= (5-1)^2- 2= 14&gt; 0. So for k> 5, k^2- 2k- 1&gt; 0 and thus k^2&gt; 2k+ 1.

thank you very much