Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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-inductively –  kuch nahi Jul 6 '11 at 2:50
add comment

8 Answers 8

up vote 12 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
5  
I'm glad you liked my comment on Eric's answer. –  Gerry Myerson Jul 6 '11 at 4:37
1  
@Geoff, you get extra credit for canceling that factor of $n$ before proceeding. –  Gerry Myerson Jul 6 '11 at 7:20
2  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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,

share|improve this answer
12  
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
add comment

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.

share|improve this answer
add comment

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)

share|improve this answer
4  
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
3  
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
    
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.