# Non inductive proof, $n!>n^3$ for $n\gt 5$

This was a trivial exercise in induction that I am unable to prove algebraically, or otherwise.

Prove that $$n!>n^3\quad\mbox{if}\quad n\gt 5$$

-
Your title says "non-inductive proof", but then you say it was an exercise in induction. Do you want an inductive proof? If so, consider the case of n=6, and the ratio of (n+1)! to n!, and (n+1)^3 to n^3. –  Doug Spoonwood Jul 5 '11 at 23:54
@Doug it was an exercise in induction, which I was able to do (it was the same as the method you mention), but I was not able to do it non-inductively –  kuch nahi Jul 6 '11 at 2:50

You could start with $n!\gt n(n-1)(n-2)(n-3)$, then you just have to prove the quartic beats the cubic.

-
After reading the comments and seeing your other answer, I have remarked the accepted answer in the interest of fairness. All the answers were correct and helpful, I just marked the one which got me immediately. –  kuch nahi Jul 8 '11 at 5:07

I think the following is the simplest approach:

If $n>5$ then $$n! \geq n (n-1)(n-2) \cdot3 \cdot 2 \,.$$

Now $3(n-2) >n$ and $2(n-1) >n$ for $n >5$, which completes the proof.

-
I'm glad you liked my comment on Eric's answer. –  Gerry Myerson Jul 6 '11 at 4:37
@Geoff, you get extra credit for canceling that factor of $n$ before proceeding. –  Gerry Myerson Jul 6 '11 at 7:20
I really didn't see Gerry's comment when I posted my answer, I wouldn't had otherwise. –  N. S. Jul 6 '11 at 23:32

For $n>5$, $n! \geq n (n-1)(n-2)(3)(2)$.

But $3(n-2)>n$ and $2(n-1)>n$, so $n!>n^3$.

-

You want $(n-1)! > n^2$ for $n > 5.$ But for $n$ in this range, $(n-1)! \geq 6(n-1)(n-2)$. Hence it suffices to show that $6(1- \frac{1}{n})(1- \frac{2}{n}) > 1$ for $n > 5.$ But $6(1- \frac{1}{n})(1- \frac{2}{n}) \geq \frac{10}{3}$ for $n > 5.$

-

If you follow the derivation of Stirling's Approximation, you get $n!\gt \sqrt{2\pi n}\left(\frac{n}{\text{e}}\right)^n$, which makes it obvious for $n \gt 3\text{e}$ or $n \gt 8$, then just check 5,6,7 by hand.

-

Hint: Take logarithms.

Then you only have to show that $$\sum_{k=2}^n \log k > 3\log n \ \ \ \text{for} \ n\geq 5.$$

Removing the middle terms, and grouping the last two with the first three, for $n\geq 6$ we have: $$\sum_{k=2}^n \log k \geq \log n +(\log(n-1)+ \log (2))+(\log(n-2)+\log(3))$$ $$\geq \log n+\log 2(n-1)+\log 3(n-2)$$ $$>\log n+\log n+\log n=3\log n.$$

Hope that helps,

-
The log's a red herring, no? This is $n!\gt n(n-1)(n-2)(3)(2)=n(2n-2)(3n-6)\gt n(n)(n)=n^3$. –  Gerry Myerson Jul 5 '11 at 23:06
He seems to have more ideas when summing things than we he multiplies things... but yeah, same idea. –  Patrick Da Silva Jul 19 '11 at 8:24
@Patrick: That is actually true... –  Eric Naslund Jul 19 '11 at 14:50

The Stolz–Cesàro theorem does for sequences what l"Hopital does for functions, and can be used to show that $n!/n^3$ goes to infinity (which isn't exactly what's wanted here, I know). The theorem says, if $a_1,a_2,\dots$ and $b_1,b_2,\dots$ are real sequences, if $b_n$ is strictly increasing and unbounded, then $$\lim{a_n\over b_n}=\lim{a_{n+1}-a_n\over b_{n+1}-b_n}$$ if the second limit exists.

Applied three times to $n!/n^3$, you get $(n^3+3n^2+5n+2)n!/6$, which clearly goes to infinity.

-

that's probably not very smart, but if you take the limit $\lim_{x \to \infty} \frac{x!}{x^3}$ and differentiate three times (L'Hospital's rule), you get a constant in the denominator and some expression that tends to $\infty$ in the numerator if you take the limit (since all n are integers and $(fg)'=f'g+fg'$ you are guaranteed to get a monotonic sum in the numerator, therefore no $\infty -\infty$ indeterminancy)

-
How do you propose to differentiate that factorial? –  Gerry Myerson Jul 6 '11 at 4:36
with digamma function –  sigma.z.1980 Jul 6 '11 at 6:57
So you reckon that someone who is having trouble finding an algebraic proof of $n!\gt n^3$ is going to be au fait with the digamma function? Actually, I'm not sure I'm sufficiently familiar with it myself to see right away how to show that the 3rd derivative of the gamma function goes to infinity. –  Gerry Myerson Jul 6 '11 at 7:18
diff(diff(diff(x!,x),x),x) gives $x!\psi(x+1)^3+3x!\psi^{'}(x+1) \psi(x+1) +x!\psi^{''}(x+1)$. The derivatives are polygamma function that are dominated by $\psi$, so the whole function tends to infinity. O agree though this is not a very strightforward way of solving the OP's problem. –  sigma.z.1980 Jul 6 '11 at 8:08