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)?
Best Answer
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.)