Prove by induction $n^2 \leq n!$ for $n\geq 4$.

Question

I managed to get $P(4):4^2 = 16 \geq 24 = 4!$

But then assuming $n^2 \geq n!, \forall n\geq4\in\mathbb{Z}$, I need to prove $(n+1)^2 \geq (n+1)!$

I tried $n^2+2n+1\geq n!\cdot (n+1)$, but I got stuck.

Any thoughts on how to continue?

Answer 1

Hint: $$n!>n^2$$ $$(n+1)!= (n+1)\cdot n! > (n+1)\cdot n^2 > (n+1)^2$$

Answer 2

To make things easier, prove that $$n+1 \leqslant n!$$ for $n\geqslant 4$. (This is straightforward.)

Recall that $(n+1)! = (n+1)n!$. So given that $n^2 \leqslant n!$, we have

$$(n+1)! = (n+1)n! \geqslant (n+1)(n+1) = (n+1)^2. $$

Answer 3

Here is the meat of the inductive proof (i.e., the inductive step): \begin{align} (k+1)! &= (k+1)\cdot k!\tag{by definition}\\[0.5em] &\geq (k+1)\cdot k^2\tag{by inductive hypothesis}\\[0.5em] &= k^3+k^2\tag{expand}\\[0.5em] &\geq k^2+2k+1\tag{since $k\geq 4$}\\[0.5em] &= (k+1)^2.\tag{factor} \end{align} That is really what you need to show for the inductive step.

Note: It may be more interesting to show that $2^n<n!$ for $n\geq 4$. [Just a thought]