Slick proof of Stirling's Formula?

Question

In Upper Limit on the Central Binomial Coefficient, Noam Elkies and David Speyer have given a nice proof that the central binomial coefficient $\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$. This can be used to derive Stirling's formula $$ a_n = \frac{n!e^n}{n^n \sqrt{n}} \sim \sqrt{2\pi} $$ by showing that $a_n$ is decreasing, hence convergent to some positive real number $c$, and computing $c$ via $$ c = \lim_{n \to \infty} \frac{a_n^2}{a_{2n}} = \sqrt{2\pi}. $$ My question is whether we can do without this roundabout tour and prove Stirling's formula directly along the lines of the proofs quoted above.

Answer 1

The proof in the OP based on the sequence $a_n$ is proof number 1 in Steve Dunbar's Dozen Proofs of Stirling’s Formula (page 8, worked out here). Is there an alternative proof based on a sequence $b_n$ that does not require knowledge of Stirling's formula to construct the sequence?

Proof number 2 in that list gives such an alternative, based on $b_n=\sum_{k=1}^n\log k=\log n!$ Approximation of the sum by the integral gives $$b_n\approx \int_0^n\log x\,dx+\text{error}=n\log n -n+\text{error}.$$ The calculation of the error term, to obtain the asymptotic $\log\sqrt{2\pi n}$, can be done using the Euler-MacLaurin formula.$^\ast$ If we prefer not to use Euler-MacLaurin, proofs number 3 and 4 start from the same sequence and then approximate the sum by an integral using the trapezoidal rule or a Taylor series. These calculations are worked out in Dunbar's notes.

$^\ast$ Dunbar credits this proof to John Todd, Introduction to the Constructive Theory of Functions (1963).

Answer 2

I've played around with this a bit. I have a slick lower bound, but not a slick upper bound.

We start with the $\Gamma$-integral: $$n! = \int_{x=0}^\infty x^n e^{-x} dx = \int_{y=-n}^\infty (n+y)^n e^{-n-y} dy$$ so $$\frac{n! e^n}{n^n} = \int_{y=-n}^\infty (1+y/n)^n e^{-y} dy. \tag{$\clubsuit$}$$

Lower bound

From $(\clubsuit)$, we have $$\frac{n! e^n}{n^n} \geq \int_{y=-n}^n (1+y/n)^n e^{-y} dy. \tag{$\diamondsuit$}$$ From the arithmetic-geometric mean inequality, $$(1-y/n)^n e^{-y} + (1+y/n)^n e^{-y} \geq 2 (1-y^2/n^2)^{n/2}$$ so, combining the values of the integrand in $(\diamondsuit)$ at $y$ and $-y$ $$\frac{n! e^n}{n^n} \geq \int_{y=-n}^n (1-y^2/n^2)^{n/2} \, dy.$$ Putting $y = n \sin \theta$, we get $$\frac{n! e^n}{n^n} \geq \int_{\theta = -\pi/2}^{\pi/2} (\cos^n \theta) (n \cos \theta) \, d \theta= n \int_{\theta = -\pi/2}^{\pi/2} \cos^{n+1} \theta \, d \theta . $$ Now, using the same trick of putting $u = \tan \theta$ as in my other answer, we get $$\int_{\theta = -\pi/2}^{\pi/2} \cos^{n+1} \theta \, d \theta = \int_{u=\infty}^\infty \frac{du}{(1+u^2)^{n/2+3/2}} \geq \int_{u=\infty}^\infty e^{-u^2 (n/2+3/2)} \, du = \frac {\sqrt{\pi}}{\sqrt{n/2+3/2}}.$$

Putting it together, $$\frac{n! e^n}{n^n} \geq \frac{\sqrt{\pi} n}{\sqrt{n/2+3/2}}$$ or $$n! \geq \frac{n^n}{e^n} \sqrt{2\pi n} \frac 1 {\sqrt{1+3/n}}.$$

Failure to get an upper bound Unfortunately, there seems to be no way to get a similar concrete upper bound for the $\Gamma$ integral. We can split $(\clubsuit)$ into $$\frac{n! e^n}{n^n} = \int_{z=0}^{n} (1-z/n)^n e^z \, dz + \int_{y=0}^\infty (1+y/n)^n e^{-y} \, dy. \qquad \tag{$\heartsuit$} $$ The first integrand is tractable: We have $$\log (1-z/n) \leq -\frac{z}{n}-\frac{z^2}{2n^2} \qquad \text{for $z>0$}$$ (since the other terms of the Taylor series are all negative) so $$(1-z/n)^n e^z \leq \exp(-z-z^2/(2n)) e^z = \exp(-z^2/(2n))$$ and $$\int_{z=0}^n (1-z/n)^n e^z \, dz \leq \int_{z=0}^n e^{-z^2/(2n)} \, dz \leq \int_{z=0}^\infty e^{-z^2/(2n)} \, dz = \frac{\sqrt{2 \pi n}} 2.$$ So the remaining task is to find a way to upper bound the second integral in $(\heartsuit)$ by $\tfrac{\sqrt{2 \pi n}} 2 (1+o(1))$. There are lots of ways to prove that this is the right asymptotic growth, but I haven't found any that yields a slick concrete inequality.

---

I skimmed through the many proofs of Stirling's formula that the Monthly has published in the last 70 years. When one starts from this approach, the usual route is to break the integral $\int_{y=0}^\infty (1+y/n)^n e^{-y} \, dy$ into two pieces, roughly at $y=cn$.

For $y<n$, one can use the bound $$\log (1+y/n) \leq \frac{y}{n} - \frac{y^2}{2n^2} + \frac{y^3}{3 n^3}$$ coming from the alternating series test; one then has to do something messy with the cube in the exponent.

For $y>cn$, there are a variety of approaches to show that $\int_{y=cn}^\infty (1+y/n)^n e^{-y} \, dy \to 0$ as $n \to \infty$. The one that I find simplest is to find a $b<1$ such that $1+u \leq \exp(bu)$ for $u>c$, and then we have $\int_{y=cn}^\infty (1+y/n)^n e^{-y} \, dy \leq \int_{y=cn}^\infty e^{-(1-b)y} \, dy$.

I haven't found anyone who just makes a slick change of variables and deals with the integral in one swoop.

Answer 3

A very elementary proof of Stirling's formula is found here or the article by M. R. Murty and K. Sampath, "A very simple proof of Stirling's formula", The Mathematics Student, Vol. 84, Nos. 1-2, January-June (2015), 129–133.

This link (Wayback Machine) outlines how this proof can be done essentially in three elementary steps, with the additional assumption that we know Wallis product formula for $\pi$ (that can be proved easily by integrating $\sin ^n (x)$, see for example the Wikipedia entry). I believe this to be the most elementary proof found anywhere. It requires nothing beyond elementary Calculus.