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 $$2^{n} \geq 2n+1$$ for
$$n \geq 5$$

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

$$k^2 > 2k+1$$

(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

$$\begin{align*} 2^{k+1} & = 2 \left(2^k\right) \ge 2\left(k^2\right)\\ & = 2k^2 = k^2 + k^2\\ & > k^2 + 2k + 1 & = (k+1)^2 \\ 2^{k+1} \ge (k+1)^2 \end{align*}$$

 

[almonz]

hi . If possible, please explain why :

k^2 > 2k +1

I dont 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> 0$. So for k> 5, $k^2- 2k- 1> 0$ and thus $k^2> 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> 0$. So for k> 5, $k^2- 2k- 1> 0$ and thus $k^2> 2k+ 1$.

thank you very much