Basic Induction Problem

Question

For $N \geq 4$, prove $2^N \geq N^2$.

I have the base case, $N=K$, and $N=K+1$ steps, but I am stuck at this point...

$2^K\cdot 2 \geq (K+1)^2$

Thanks!

Answer 1

You've already done the base case, so let's do the induction step.

Induction Hypothesis: Suppose that $2^N \geq N^2$ for $N = K$, where $K \geq 4$.

It remains to prove that $2^{K+1} \geq (K+1)^2$. Indeed, observe that: \begin{align*} 2^{K+1} &= 2(2^K) \\ &\geq 2(K^2) &\text{by the induction hypothesis} \\ &= K^2 + (\color{red}{K})K \\ &\geq K^2 + (\color{red}{4})K &\text{since } K \geq 4 \\ &= K^2 + 2K + 2(\color{red}{K}) \\ &\geq K^2 + 2K + 2(\color{red}{4}) &\text{since } K \geq 4 \\ &> K^2 + 2K + 1 &\text{since } 8 > 1 \\ &= (K+1)^2 \end{align*} as desired. $~~~\blacksquare$

Answer 2

Your last line is unjustified. You shouldn't write anything that you haven't justified. Instead, you can write "If $2^K > K^2$, then $2^{K+1}$ ...".

Answer 3

You need to show: $2K^2 \geq (K+1)^2$