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

1. Apr 30, 2008

dtl42

1. The problem statement, all variables and given/known data
Prove that $$2^{x} \geq x^{2}$$
$$\forall x\geq5$$

2. Relevant equations
$$2^{k} \geq x^{k}$$

3. 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.

2. Apr 30, 2008

steelphantom

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

Last edited: Apr 30, 2008
3. Apr 30, 2008

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.

4. May 1, 2008

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.

5. May 1, 2008

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?

6. May 1, 2008

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$$

7. May 1, 2008

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".

Last edited by a moderator: May 1, 2008
8. May 1, 2008

Diffy

9. Sep 26, 2008

rwx1606

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

10. Sep 26, 2008

Dick

RHS=Right Hand Side (of the equation).

11. Sep 26, 2008

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).

12. Sep 27, 2008

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, 25= 32> 25= 52 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$

Last edited by a moderator: Nov 15, 2011
13. Sep 28, 2008

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 \tag{From earlier point}\\ & = (k+1)^2 \\ \intertext{Therefore} 2^{k+1} \ge (k+1)^2 \end{align*}

14. Nov 15, 2011

almonz

hi . If possible, please explain why :

k^2 > 2k +1

I dont understand it .

15. Nov 15, 2011

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$.

16. Nov 15, 2011

almonz

thank you very much