Prove by induction that $n^2How can I show that $n^2<n!$ for all $n\geq 4$
Step 1
For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$<$ RHS.
Step 2
Suppose the result be true for $n=k$  i.e.,
$k^2<k!$
Step 3
For $n=k+1$
$(k+1)^2=k^2+2k+1$
What will be the next step?
 A: If $k!>k^2$
$\implies(k+1)!=(k+1)\cdot k!>(k+1)k^2$
It is sufficient to show $(k+1)k^2\ge(k+1)^2\iff k^2\ge k+1$
$\iff k(k-1)\ge1$ which is true if $k\ge2$
A: I'll just provide the "meat" of the induction proof:
\begin{align}
(k+1)! &= (k+1)k!\tag{by definition}\\[0.5em]
       &> (k+1)k^2\tag{by induction hypothesis}\\[0.5em]
       &= k^3+k^2\tag{expand}\\[0.5em]
       &> k^2+2k+1\tag{since $k\geq 4$}\\[0.5em]
       &= (k+1)^2.\tag{factor}
\end{align}
A: Since $n!=n\cdot (n-1)!$ and $n^2=n\cdot n$, it suffices to prove $n<(n-1)!$, which follows from $(n-1)!\ge 2(n-1)$ [as $2$ and $n-1$ are two distinct factors in the product making up $(n-1)!$ for $n\ge 4$] and $2(n-1)> n$ [for $n>2$].
A: For $k \geq 4$, assume $k^2 \leq k!$. Then we have
$$(k+1)^2 = (k+1) \times \frac{k+1}{k^2} \times k^2 \leq (k+1) \times \frac{2k}{k^2} \times k! \leq (k+1)! \times \frac{2}{k} \leq (k+1)!$$
A: One more way (without induction): $\log x$ is a monotone increasing function, so if we log both sides, the resulting inequalities will hold for the original functions. Look at 
$$
2 \log n = \log n +\log n 
$$
on LHS. On the RHS you have $\sum_{k=1}^{n} \log k = \log 1 + \log 2 +\ldots \log n$. Subtract $\log n $ from both sides. The remaining term on LHS is $\log n$. Compare it to $\log (n-1) + \log (n-2)$: subtract $\log (n-1)$ to get $\log \bigg( \frac{n}{n-1} \bigg)$ on LHS and $\log (n-2)$ on RHS. Now exponentiate. Clearly $\frac{n}{n-1}<n-2 \ \forall \ n \geq 4$. The remaining terms on RHS $\sum_{k=1}^{n-3} \log k$ >0. Inequality proven.
A: Suppose $$n^2<n!,$$ then we have $$(n+1)^2=n^2+2n+1<n!+(2n+1)<n!+n.n!=(n+1)!$$ for $$2n+1<n.n!\iff n+1\ge 4.$$
