Question: For which values of n, $n^2 \leq 2^n$ holds? Prove it by simple induction.

This is what I have done so far:

We know that all natural numbers other than 3 works. So I will make the claim that $\forall n \in \mathbb{N}, n \neq 3: n^2 \leq 2^n$

Now to prove this:

Proof method: Simple induction

Let P(n) be that $\forall n \in \mathbb{N}, n \neq 3: n^2 \leq 2^n$.

Basic Step:

$5^2 = 25 \leq 2^5 = 32$

Then P(5) is true, because $5^2 \leq 2^5$

Inductive Step:

Assume $\forall k \in \mathbb{N}, k \neq 3: k^2 \leq 2^k$

Want to show that $P(k) \implies P(k+1)$

So, $k^2 \leq 2^k$

$2k^2 \leq 2(2^k)$

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

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

This is where I got stuck, trying to change the left hand side to $(k+1)^2$, I've tried working with the idea that $(k+1)^2 = k^2 + 2k + 1$, but wasn't able to really get anything out of it.

Any help will really be appreciated.

  • $\begingroup$ You just need $2k^2\geq (k+1)^2$, that is equivalent to $(k-1)^2\geq 2$. $\endgroup$ Sep 18 '16 at 22:18

For your base case, I recommend you show that $n^2 \le 2^n$ works for $n=1$, $n=2$, and $n=4$ as well. If you show $n=4$, showing $n=5$ is unnecessary (since your induction step will take care of that).

About your inductive step, you ended with:

$$2k^2 \le 2^{k+1}$$

You now need to show $(k+1)^2 \le 2k^2$, which implies that $(k+1)^2 \le 2^{k+1}$, which is what you want to show. Then we see that:

$$4 \le k$$ $$1+\sqrt{2} \le k$$ $$2 \le (k-1)^2$$ $$2k+1 \le k^2$$ $$k^2+2k+1 \le 2k^2$$ $$(k+1)^2 \le 2k^2$$ $$(k+1)^2 \le 2^{k+1}$$


We assume $k^2<2^k$ for some value of $k$. From there:




$k^2<2^k$ by our assumption, so we are now left with:



From basic algebra, if $a<b$ and $c<d$, then $a+c<b+d$.

Letting $a=2k+1$, $b=d=2^k$, and $c=k^2$ should prove the theorem. Q.E.D.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.