Prove by induction that $n^2<n!$

How 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?

Solution 1:

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$

Solution 2:

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$].

Solution 3:

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}

Solution 4:

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)!$$

Solution 5:

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.