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

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

## Answers and Replies

Related Precalculus Mathematics Homework Help News on Phys.org
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:
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.

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
Science Advisor
Homework Helper
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?

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
Science Advisor
Homework Helper
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:

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

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

Dick
Science Advisor
Homework Helper
RHS=Right Hand Side (of the equation).

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
Science Advisor
Homework Helper
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:
statdad
Homework Helper
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*}

Last edited by a moderator:
hi . If possible, please explain why :

k^2 > 2k +1

I dont understand it .

HallsofIvy
Science Advisor
Homework Helper
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$.

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