Show that $n^2<n!$ for all $n\geq 4$

Question

Show that $n^2<n!$ for all $n\geq 4$

What I did was

Base case:

$4^2<4!\iff16<24$

Inductive hypothesis:

Being that for a $n\leq k$, the equation remains true, we prove for $k+1$

$$\begin{align*}k^2+(k+1)^2&<(k+1)!\\ \iff k^2+(k+1)^2&<(k+1)*k!\end{align*}$$

as $k!>k^2$, summing $(k+1)^2$ will be also less than multiplying by $k+1$.

However, I don't know if this is correct or complete at all. Am I missing anything?

Answer 1

You assume $k^2 <k!$ and want to show result is true for $n=k+1.$ That is you want to show $(k+1)^2<(k+1)!.$

Consider $$\begin{align*}(k+1)!&=(k+1)k!\\ &>(k+1)k^2\qquad \text{(induction hypothesis)}\\ &>(k+1)(k+1)\qquad \text{(since } k^2>k+1)\\ &=(k+1)^2.\end{align*}$$

Answer 2

This is a great start! From the first line of your chain of inequalities, it looks like you're trying to prove $k^2 + (k + 1)^2 < (k + 1)!$, which is false, instead of $(k + 1)^2 < (k + 1)!$, and your last step isn't very clear (why is adding $(k + 1)^2$ less than multiplying by $k + 1$?). The right way to set up this proof is to assume that $k^2 < k!$ is true, and try to prove that $(k + 1)^2 < (k + 1)!$.

So you can set up a chain of inequalities that you're trying to prove: \begin{align} (k + 1)! & = (k + 1) \cdot k! \\ & \vdots \\ & > (k + 1)^2 \end{align}

Can you fill in the details of the proof? The first step should be applying the inductive hypothesis that $k! > k^2$.

Answer 3

Do you have to use the induction? If you consider $$ \frac{n!}{n^2} \geq \frac{(n-1)!}{n} \geq \frac{(\frac{n}{2})^{\frac{n}{2}}}{n} = \frac{n^{\frac{n}{2}-1}}{2^{\frac{n}{2}}} \geq 1 \ \text{for} \ n \geq 4 $$