Prove by induction that $2^n > n^2$

Question

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck.

I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then follows to turn it into $k^2+4n$ and then $k^2+2k+1$. Was the $K$th step used because I cant understand how it was used in case.

Answer 1

Inductive hypothesis: For $n = k$, $$\color{blue}{2^k \geq k^2},\quad k \geq 4.$$

$$2^{k+1} = 2\cdot \color{blue}{2^k} \geq 2(\color{blue}{k^2}) \geq k^2 + k^2 \geq k^2 + 2k + 1 \overset{\large k>2} = (k+1)^2$$

Answer 2

Induction problems like this can be done mechanically by telescopy. Rewriting $\,f(n) = 2^n-n^2\,$ as a telescopic sum of its differences makes its positivity obvious, because each summand is $\color{#c00}{\ge 0}.$

$$\displaystyle\begin{eqnarray}n\ge 5\ \ \Rightarrow\ \ \ f(n) &=&\! f(5)\,+ \sum_{\large k\,=\,5}^{\large n-1}\ (f(k\!+\!1)-f(k))\\ \displaystyle\Rightarrow\ \ \ 2^n-n^2 &=& \ 7\ +\ \sum_{\large k\,=\,5}^{\large n-1}\, (\overbrace{2^{k}- (2k\!+\!1)}^{\large \color{#c00}{\ge 0}})\, >\, 0 \end{eqnarray}\qquad$$

That the overbraced term is $\color{#c00}{\ge 0}\,$ is obvious by induction (telescopic or not). Note that it fails for $\,n < 5,\,$ e.g. $\,f(4) = 0,\ f(3) = -1.\ $

For further discussion see my many posts on telescopic induction.