Proof By Induction $2^n \ge n^2$ for $n\ge4$

Question

I am trying to prove the following, and here is what I have done: Can somebody help to complete this?

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

$n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE

Assume True for $n=k$, for $k\ge 4$

$2^k \ge k^2$

Should be true for $n=k+1$ for $k\ge 4$

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

by Assumption: $2^k \ge k^2$, multiplying both sides by $2$

$2\cdot 2^k \ge 2\cdot k^2$

$2^{k+1} \ge k^2 + k^2$ Where would I got from here?

Answer 1

mathlove's answer addresses the core part of the induction step. It seems like you're still struggling though; thus, I'll try to flesh things out a bit more. Let me know if a step(s) does not make sense.

---

For $n\geq 4$, let $S(n)$ denote the statement $$ S(n) : 2^n\geq n^2. $$ Base step ($n=4$): $S(4)$ says that $2^4=16\geq 16=4^2$, and this is true.

Inductive step: Fix some $k\geq 4$ and assume that $S(k)$ is true where $$ S(k) : \color{blue}{2^k\geq k^2}. $$ To be shown is that $S(k+1)$ follows where $$ S(k+1) : \color{green}{2^{k+1}\geq (k+1)^2}. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} \color{green}{2^{k+1}} &= \color{blue}{2^k}\cdot 2\tag{by definition}\\[0.5em] &\geq \color{blue}{k^2}\cdot 2\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &\geq k^2+2k+1\tag{since $k\geq 4$; see $(\dagger)$}\\[0.5em] &= \color{green}{(k+1)^2}, \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 4$.

---

$(\dagger)$: We have the following: $$ k^2\cdot 2\geq k^2+2k+1\Longleftrightarrow k^2-2k-1>0, $$ and this is certainly true when $k\geq 4$ isn't it?

Answer 2

Just compare $k^2 + k^2$ with the term you want, namely $(k+1)^2 = k^2 + 2k + 1$. Does $2k+1 \lt k^2$ always hold? For $k$ large enough at least? If yes, you only need to solve that new problem.

And how do you solve that problem? By induction! :) (“induction proof within an induction proof” may sound complicated, but you can just start with a lemma “$2k+1 \lt k^2$ for all $k \gt …” and then use that lemma in your proof.)

Answer 3

Since $k\ge 4$, one has $$\begin{align}2^{k+1}&\ge k^2+k^2\\&\ge k^2+4k\\&=k^2+2k+2k\\&\ge k^2+2k+2\cdot 4\\&\ge k^2+2k+1\\&=(k+1)^2\end{align}$$