Prove by induction that $n^2 < 2^n$ for all $n \geq 5$? So far I have this:
First consider $n = 5$. In this case $(5)^2 < 2^5$, or $25 < 32$. So the inequality holds for $n = 5$.
Next, suppose that $n^2 < 2^n$ and $n \geq 5$. Now I have to prove that $(n+1)^2 < 2^{(n+1)}$.
So I started with $(n+1)^2 = n^2 + 2n + 1$. Because $n^2 < 2^n$ by the hypothesis, $n^2 + 2n + 1$ < $2^n + 2n + 1$. As far as I know, the only way I can get $2^{n+1}$ on the right side is to multiply it by $2$, but then I get $2^{n+1} + 4n + 2$ on the right side and don't know how to get rid of the $4n + 2$. Am I on the right track, or should I have gone a different route?
 A: There are, of course, many ways to force $2^{n + 1}$ to show up on the RHS. I like to bound the lower order terms as multiples of the leading term by repeatedly applying the given inequality $n \geq 5$ so that I can apply the inductive hypothesis in one shot. Indeed, observe that:
\begin{align*}
(n + 1)^2
&= n^2 + 2n + 1 \\
&< n^2 + 4n + 5 \\
&\leq n^2 + 4n + n &\text{since } n \geq 5 \\
&= n^2 + 5n \\
&\leq n^2 + (n)n &\text{since } n \geq 5 \\
&= 2(n^2) \\
&< 2(2^n) &\text{by the inductive hypothesis} \\
&= 2^{n + 1}
\end{align*}
as desired.
A: Remark that
$$2^{n+1} = 2 \cdot 2^n > 2 n^2 = n^2 +n^2> n^2+2n+1 = (n+1)^2.$$
Indeed $n^2-2n-1=(n-1)^2-2>0$ for $n \geq 5$.
A: The base case is clear. The inductive step is done as follows. Suppose it holds for some $k\geq5$. That is, $k^2<2^k$
We know $(k+1)^2<2k^2 \Longleftrightarrow \frac 12 (k+1)^2 - k^2 < 0$ for $k\geq 5$ (this can be shown rigorously determining the roots of the polynomial and noting that it changes sign only at those roots). 
Then we have inequalities $(k+1)^2 <2k^2 < 2 \cdot 2^k = 2^{k+1}$
A: First, we prove a simple lemma. 
$$ 
\begin{align}
n & \gt 5\\ 
\implies n-1 &\gt 4\\ 
\implies (n-1)^2 &\gt 16 \gt 2 \\
\implies n^2 - 2n + 1 &\gt  2\\ 
\implies n^2 &\gt 2n +1\\
\end{align}
$$ 
Now, we start with our induction step. 
$$
\begin{align}
n^2 &\lt 2^n \text{ From hypothesis}\\ 
\implies 2n^2 & \lt 2^{n+1}\\
\implies n^2 + n^2 &\lt 2^{n+1}\\ 
\implies n^2 + 2n + 1 &\lt 2^{n+1} (n^2 \gt 2n+1)\\ 
\implies (n+1)^2 &\lt 2^{n+1} \\
\end{align}$$
