Prove the following: For n ≥ 4, n ^2 ≤ 2^n

Question

I have been asked to prove the following:

For n ≥ 4, n$^2$ ≤ 2$^n$

I will argue by induction the statement P(k): for n ≥ 4, n$^2$ ≤ 2$^n$.

First, consider the base case P(4) = 16 ≤ 16 which is true, so we assume P(n) holds and consider P(n+1).

2$^{n+1}$ = 2$^n$2

We know that 2$^n$2 ≥ 2$^n$ and from our induction hypothesis we also know that n$^2$ ≤ 2$^n$, so we know that 2$^n$2 ≥ 2$^n$ ≥ n$^2$.

This is the part that makes me a bit uncomfortable and I think is wrong:

(n+1)$^2$ ≥ 2$^n$ by our induction hypothesis and definition of inequality.

Then, also by definition of inequality:

2$^n$2 ≥ (n+1)$^2$ ≥ 2$^n$ ≥ n$^2$

Thus, we have completed our induction step and shown that 2$^{n+1}$ ≥ (n+1)$^2$.

I am worried about my jump that (n+1)$^2$ ≥ 2$^n$. Do I need to some kind of subproof here to prove this relation? Any help would be appreciated!

Answer 1

Observe the following:

$$\begin{align} n\geq 4&\implies n^2\geq 4n\\ &\implies n^2\geq 2n+2n\\ &\implies n^2> 2n+1. \end{align}$$ $P(n)$ is assumed to be true and so, $$2^n\geq n^2$$ and so multiplying by $2$ to both sides, we get $$2^{n+1}\geq 2n^2.$$ Thus, if $n\geq 4$ we get

$$\begin{align} 2^{n+1}&\geq 2n^2\\ &=n^2+n^2\\ &>n^2+(2n+1)\\ &=(n+1)^2 \end{align}$$ This means that $P(n+1)$ is also true.

Answer 2

Hint For $n\ge 4$ you know that $(n+1)/n = 1 + 1/n \le 5/4$ so $(n+1)^2/n^2 \le 25/16 \le 2.$

Answer 3

This is more a comment than an answer, but it does provide an answer.

In my answer to my own question, I prove this:

If $n$ and $k$ are integers and $k \ge 2$ and $n \ge k^2+1$, then $2^n > n^k$.

Here it is:

Prove that $n^k < 2^n$ for all large enough $n$