3
$\begingroup$

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$

  • 1
    @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-inductively2011-07-06

8 Answers 8

1

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)

  • 0
    There's actually a theorem that does for sequences what L'Hopital does for functions, replacing derivatives with finite differences. You can use it to do this problem without digammas. I'm going to write up an answer using it.2011-07-08
17

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.

  • 2
    I really didn't see Gerry's comment when I posted my answer, I wouldn't had otherwise.2011-07-06
12

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

  • 0
    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.2011-07-08
6

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

5

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

4

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.

4

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,

  • 0
    @P$a$trick: That is actually true...2011-07-19
4

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.