Proof of $2^n \ge n^2 $ for $n \ge 4 $

Question

I am currently learning induction and I understand the proof except the last line: $$ 2^{n+1} \ge (n+1)^2$$

I'm aware of the fact that, at some point (here $n=4$) an exponential function grows faster than a polynomial function ... but wouldn't I have to prove this too?

Answer 1

You can show that $lim\frac{2^n}{(n^2)} = \infty$ as $n \rightarrow \infty$. This is one of the ways to show that $2^n $ "grows faster" than $n^2$.

Proof:

From l'Hospital's rule (using it twice) we have: $\lim\limits_{n \to \infty}\frac{2^n}{n^2}=\lim\limits_{n \to \infty}\frac{2^n log2}{2n}=\lim\limits_{n \to \infty}\frac{2^nlog^22}{2}=\infty.$

Using l'Hospital's rule is legal as we have the expression $\frac{\infty}{\infty}$.

Answer 2

Induction:

1. $n=4$ is ok, because $16\ge16$.
2. Let's say it works for some $k\ge4$. Then $2^k \ge k^2$
3. Now we get $2^{k+1}\ge 2^k*2 \ge k^2*2$ and $2k^2\ge(k+1)^2=k^2+2k+1$, because: $k^2-2k-1\ge0 \Leftrightarrow (k-1)^2-2\ge0\Leftrightarrow k\ge3. $ So $2^{k+1}\ge (k+1)^2$. And we've got what we wanted to get.

Answer 3

Base case:

If $n=4$, $2^{n} \geq n^2 \Rightarrow 16 \geq 16$ which is true.

Induction Step:

Assume the inequality holds for some $n$, does this imply it also holds for $n+1$?

Well, if we have $2^{n} \geq n^2$ we can start by multiplying by $2$ giving:

$2\cdot2^{n} \geq 2\cdot(n)^2$ which implies:

$2^{n+1} \geq 2 n^2$ so if the right side is $\geq(n+1)^2$ we are sorted.

Check it:

$2n^2 \geq (n+1)^2 \Rightarrow 2n^2 \geq n^2 +2n+1 \Rightarrow (n-1)^2\geq 0$ which is certainly true for $n\geq4$.