# Prove that n squared is less than or equal to 2 to the n by induction. [duplicate]

I've been asked to prove by induction that $$n^2\leq 2^n$$, and told it is true $$\forall n\in \mathbb{N},n>3$$

I think I have found the right way to the proof, but I'm not sure since I get stuck half-way there. What I did was taking a base case of $$n=4$$ and tested it, and it resulted to be true. Then I assumed it would be true for some number $$k$$, such that $$n=k$$ and $$k^2\leq 2^k$$, and attempted to prove

$$(k+1)^2 \leq 2^{k+1}$$

And this is how I attempted to prove this. First of all, I started with my assumption.

$$=k^2\leq 2^k$$

$$=2k^2\leq2^{k+1}$$

Then I tried to prove that $$(k+1)^2 \leq 2k^2$$, for this would imply my thesis, i.e. $$(k+1)^2\leq2^{k+1}$$. So I went forth on my effort:

$$(k+1)^2≤2k^2$$

$$=k^2+2k+1\leq2k^2$$

$$=2k+1\leq k^2$$

(By assumption)

$$=2k+1\leq 2^k$$

Now that I simplified it, I need to prove this is true; this is, prove that $$(k+1)^2 \leq 2k^2$$. So I take a base case of $$n=4$$ and in deed it satisfies the inequality. So I assume it is true for some number $$j, k=j$$ and try to prove it. Nevertheless I have failed in trying to prove this, I don't really know if my steps so far are right or wrong. Is my reasoning okay? And if its, how can I prove $$2k+1\leq 2^k$$? Thank you in advance.

## marked as duplicate by dantopa, Cesareo, Lee David Chung Lin, Eevee Trainer, LeucippusMar 27 at 4:57

• This question has been asked so many times already. Please make an attempt to search for the problem. math.stackexchange.com/questions/319913/proof-that-n2-2n/…, math.stackexchange.com/questions/263825/…, math.stackexchange.com/questions/263825/… – JavaMan Mar 26 at 17:30
• – JavaMan Mar 26 at 17:30
• When you realize that you must prove $2k + 1<k^2$ !!!! DONT !!! go back to your assumption to prove $2k+1 < 2^k$. For one thing proving $2k + 1< 2^k$ won't prove $k^2 < 2k + 1 < 2^k$ is impossible, but more importantly, you got here via the assumption. Going back will be circular. You have gotten to the "practical world" where proving $2k+1< k^2$ is your direct way of proving your proposition. So prove it directly. Prove $2k + 1 < k^2$. That should be easy. – fleablood Mar 26 at 17:37
• ... for one thing $k^2 -2k - 1= k^2 - 2k + 1 - 2=(k-1)^2 - 2\ge 3^2 -2 = 7 > 0$ so $k^2 > 2k + 1$. – fleablood Mar 26 at 17:43

You need to prove $$2k + 1 \le k^2$$.

Do it this way: $$1 < k$$ so $$2k + 1 < 2k + k = 3k$$. And $$3 < k$$ so $$3k < k^2$$.

So to put it together:

Induction step:

If $$k^2 < 2^k; k > 3$$ then

$$(k+1)^2 = k^2 + 2k + 1 <$$

$$k^2 + 2k + k = k^2 + 3k <$$

$$k^2 + k*k = 2k^2 <$$

$$2*2^k = 2^{k+1}$$.

.....

.... or simply note...

$$2k + 1 < k^2 \iff$$

$$1 < k^2 - 2k \iff$$

$$2 < k^2 - 2k + 1 = (k-1)^2$$.

And $$k-1 \ge 3$$ the $$(k-1)^2 \ge 9 > 2$$.

• Such a neat reasoning, I feel silly I couldn't do this myself, haha. Excelent, @fleablood, I appreciate the fact that you took the trouble to answer my question. Thank you! – Lafinur Mar 26 at 19:30
• The last line in the first part should probably read $2*2^k \color{red}= 2^{k+1}.$ – CiaPan Mar 26 at 20:36
• ooppps......... – fleablood Mar 26 at 21:08