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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 6

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,

Answer 7

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.

Answer 8

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)