# How best to explain the $\sqrt{2\pi n}$ term in Stirling's?

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)?

• 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. Feb 26, 2011 at 18:30

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

• 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. Feb 26, 2011 at 17:47
• @Qiang: unfortunately I do not. Feb 26, 2011 at 18:03
• @Qiang: Enjoy. Apr 10, 2011 at 18:13

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

• There is a saying that any analyst worth his salt can do wonders with only Cauchy-Schwarz and integration by parts. Nov 18, 2011 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?

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.

• 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. Feb 26, 2011 at 7:14

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.

I would definitely keep $$\sqrt{n}$$ and $$\sqrt{2\pi}$$ apart.

Explanation for $$\sqrt{n}$$ is that subsequently $$n^{n+\frac1{2}}$$ is a better approximation than purely $$n^n$$.

For $$\sqrt{2\pi}$$ the best explanation is that $$\sqrt{\pi}$$ is coming from $$\frac{1}{2}!$$ and there is a connection with integrals in this form

$$\int_0^1 (1-\sqrt[n]x)^m dx = \frac{m!n!}{(m+n)!}$$

which is coming to for $$m=n=\frac1{2}$$

$$\int_0^1 \sqrt{1-x^2} dx = \frac1{2}!^2 = \frac{\pi}{4}$$

because it is nothing more than a formula for area of the circle.

And about where the connection between factorial and the above exponential form is coming from, it is simply from a binomial theorem, which is valid even for non-integer values:

$$(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$$

$$(a+b)^x=\sum_{k=0}^{\infty}\binom{x}{k}a^{x-k}b^{k}, |a|>|b|$$