Prove that $n^2 < 2^n$ for all $n \geq 6$

Question

My approach to solving this: By induction.

(1) $S(n) = (n^2 < 2^n)$ for all $n \geq 6$, $n \in \mathbb N$.

(2) Base Case: $n = 6$

$$6^2 < 2^6$$ $$36 < 64$$

So the statement is true for $n = 6$. Thus it has been shown that $S(6)$ holds.

(3) Induction Hypothesis: Assume $S(n)$ holds for some $n$.

$$S(n) = (n^2 < 2^n)$$

(4) Inductive Step: Show that $S(n+1)$ holds.

$$\begin{align} (n+1)^2 &< 2^{n+1} \\ n^2 + 2n + 1 &< 2^{n+1} \\ n^2 + 2n + 1 &< 2 \cdot 2^{n} \end{align}$$

At this point I have no idea how to proceed. Could anyone give me a hint on how to proceed with what I have so far?

Answer 1

You know a relationship between $2^k$ and $k^2$; namely, $$2^k > k^2$$

according to the induction hypothesis. You also know how $2^{k}$ and $2^{k + 1}$ are related, since $2^{k + 1} = 2 \cdot 2^k$. Thus,

$$2^{k + 1} = 2 \cdot 2^{k} > 2 k^2$$

So you're ultimately trying to show that

$$2k^2 \ge (k + 1)^2$$

for $k \ge 6$. Can you complete the argument from here?