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.

By the inequality here or using integration I can get the following lower bound for $\log(n!)$. How can I get a better lower bound for $\log(n!)$?

$$\log(n!)>\log\left(\frac{(n+1)^n}{e^n}\right)$$

share|improve this question
4  
The log's in your question are superfluous. You are essentially lower-bounding $n!$. There are very good lower-bounds, notably Sterling's approximation gives $n! > \sqrt{2\pi n}(n/e)^n$. –  Fixee Mar 27 '11 at 6:41
    
I think you can develop that bound by looking at the Euler-McLaurin summation of $\sum_{k=1}^n \log k$. –  Raskolnikov Mar 27 '11 at 9:10
    
Re Fixee's comment, see en.wikipedia.org/wiki/…. –  Did Mar 27 '11 at 9:45
add comment

1 Answer

It might be worth spelling out the geometric picture behind Stirling's approximation.

On the one hand, take the integral $\int_1^{n} \log t dt$ and bound it from below by $n-1$ trapezoids, where the vertices of the $k$-th trapezoid are $(k,0)$, $(k+1, 0)$, $(k, \log k)$ and $(k+1, \log (k+1))$.

So $$\int_1^n \log t dt \geq \sum_{k=1}^{n-1} \frac{\log k + \log (k+1)}{2} = \log n! - \frac{\log n}{2}$$ That gives $$(n \log n -n) - (1 \log 1 - 1) + 1/2 \log n = (n+1/2) \log n - n + 1\geq \log n!.$$

To get a bound the other way, we'll approximate $\int_{3/2}^{n+1/2} \log t dt$. We again use a sequence of trapezoids. Our trapezoids have vertices at $(k-1/2, 0)$, $(k+1/2, 0)$, $(k-1/2, \log k - s)$ and $(k+1/2, \log k+s)$, for $2 \leq k \leq n$. Here $s$ is chosen so that the line through $(k \pm 1/2, \log k \pm s)$ is the tangent line to $\log t$ at the point $(k, \log k)$. (Explicitly, $s = 1/(2 \log k)$, but we don't need this.) This gives the bound $$\int_{3/2}^{n + 1/2} \log t dt \leq \sum_{k=2}^n \log k = \log n!.$$

So $$(n+1/2) \log (n+1/2) - (n+1/2) - (3/2) \log (3/2) + 3/2 \leq \log n!$$ or $$ \log n! \geq (n+1/2) \log (n+1/2) - n + 1-(3/2) \log (3/2) = $$ $$(n+1/2) \log n - n + (n+1/2) \log (1+1/(2n)) + 1- (3/2) \log (3/2) \geq$$ $$(n+1/2) \log n -n + (n+1/2) (1/(2n) - 1/(8n^2)) + 1- (3/2) \log (3/2) \geq $$ $$(n+1/2) \log n - n +3/2 - (3/2) \log (3/2) + 1/(8n).$$

Between the second and third line, I have bounded $\log (1+x)$ below by $x-x^2/2$, the first two terms of the alternating series for $\log$. Note that $1 > \log \sqrt{2 \pi} \approx 0.91894 > (3/2) - (3/2) \log (3/2) \approx 0.89180$, so our results are compatible with the greater precision given by Stirling's formula.

I should make pictures but I'm lazy, so I'll leave this community wiki and hope that someone else does.

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