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.

I recently showed my Algorithms class how to bound $\ln n! = \sum \ln n$ by integrals, thereby obtaining the simple factorial approximation

$$ e \left(\frac{n}{e}\right)^{n} \leq n! \leq en\left(\frac{n}{e}\right)^{n} $$

But one student, having seen Stirling's approximation, asked where the $\sqrt{2 \pi n}$ term comes from in

$$ n! \sim \left(\frac{n}{e}\right)^n \sqrt{2 \pi n} $$

which I couldn't readily answer. Looking around, I can't find a straightforward and intuitive explanation. Can someone explain this in terms understandable to a Computer Science undergrad (ie, no analysis beyond first-year calculus)?

share|improve this question
    
Sterling's formula is typically derived from the Gamma function, so you will probably be interested in this post on the intuition behind the Gamma function. See in particular the 2nd to last paragraph in George's answer. –  Matt Calhoun Feb 26 '11 at 18:30

5 Answers 5

up vote 17 down vote accepted

This blog post by Terence Tao explains how to get this constant from the central limit theorem (equivalently, from the normalization factor we use to define the normal distribution). The question remains where it came from in the central limit theorem, and I think the most honest answer to that question is Fourier analysis; $\frac{1}{\sqrt{2\pi}}$ is the normalization factor which makes the Fourier transform and its inverse look the same, and the Gaussian distribution is its own Fourier transform.

(That is, I don't think you should look for a straightforward and intuitive explanation because I think this is actually a rather deep fact which is not really explained in most courses. On the other hand, just the $\sqrt{n}$ term is straightforward to explain: instead of using the left Riemann sum or the right Riemann sum, you use the trapezoid rule.)

share|improve this answer
1  
Do you know where to find "article of Joe Keller" referred in Tao's post? The link does not seem to work any more. Thanks. –  Qiang Li Feb 26 '11 at 17:47
    
@Qiang: unfortunately I do not. –  Qiaochu Yuan Feb 26 '11 at 18:03
4  
@Qiang: Enjoy. –  J. M. Apr 10 '11 at 18:13

I'm not exactly sure how much analysis is covered by first-year calculus, but this is probably the shortest proof I know of this fact. It doesn't go very far in terms of making this intuitive, though, and I don't know that this can be done at all.

share|improve this answer

I think that the most intuitive explanation of this factor is as the total mass of a Gaussian integral in the evaluation of the stirling formual by means of steepest descent on the Gamma function defining integral. See, for example, section 2.4 of the following lecture note.

share|improve this answer
2  
If all you want is the constant $\sqrt{2\pi}$, you can get it by using the normal approximation to approximate the central binomial coefficient. –  Yuval Filmus Feb 26 '11 at 7:14

One way is to apply Euler-McLaurin Summation (which can be viewed as a clever application of repeated integration by parts) to $\displaystyle \log x$ to show that

$$n! \sim C \sqrt{n} \left(\frac{n}{e}\right)^n$$

Then use Wallis formula (another clever application of integration by parts)

$$\frac{\pi}{2} = \frac{2}{1} \times \frac{2}{3} \times \frac{4}{3} \times \frac{4}{5} \dots $$

to show that $\displaystyle C = \sqrt{2\pi}$.

If I recall correctly, this is how this was derived historically.

Of course, this does not give an intuitive reason as to why the constant is $\displaystyle \sqrt{2\pi}$

share|improve this answer
3  
There is a saying that any analyst worth his salt can do wonders with only Cauchy-Schwarz and integration by parts. –  Ragib Zaman Nov 18 '11 at 11:33

If You want to see the connection between the term $\sqrt{\pi}$ and factorial, explained in the geometric terms, You can watch Knuth's lecture entitled Why Pi?

share|improve this answer

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.