# Stirling's Formula normalization

An obvious way to get estimates on $n!$ is to compare $\sum\log k$ to $\int\log t$. If one could get Stirling's formula this way that would strike me as the "right" proof, because it would be clear why it works.

This morning I came much closer to this than I have in the past; in fact fairly straightforward comparisons of sums to integrals show that $$n!\sim c\sqrt n\left(\frac ne\right)^n.$$

Question: I wonder if there's some cheap trick to show that if $n!\sim c\sqrt n(n/e)^n$ then $c=\sqrt{2\pi}$.

• The usual cheap trick is to use Wallis's product formula for $\pi$. – Lord Shark the Unknown Aug 1 '18 at 16:22
• Another relatively straightfoward way would be to calculate the normalization for the Gaussian approximation to the binomial distribution. – joriki Aug 1 '18 at 16:32

You could calculate the normalization for the Gaussian approximation to the binomial distribution.

A Cheap Method

As a function of $k$, $\frac{n^k}{k!}$ reaches its maximum when $k=n-1$ and $k=n$. Furthermore, \begin{align} \log\left(\frac{n^k}{k!}\frac{n!}{n^n}\right) &\stackrel{k\lt n}{=}\log\left[\left(1-\frac0n\right)\left(1-\frac1n\right)\cdots\left(1-\frac{n-k-1}n\right)\right]\\ &\stackrel{k\gt n}{=}\log\left[\frac1{1+\frac1n}\frac1{1+\frac2n}\cdots\frac1{1+\frac{k-n}n}\right] \end{align} Both of these give a second order difference asymptotic to $-\frac1n$.

Therefore, applying Laplace's Method, we get \begin{align} e^n\frac{n!}{n^n} &=\sum_{k=0}^\infty\frac{n^k}{k!}\frac{n!}{n^n}\\ &\sim\int_{-\infty}^\infty e^{-\frac{x^2}{2n}}\,\mathrm{d}x\\[9pt] &=\sqrt{2\pi n} \end{align}

A More Detailed Method

For $k\lt n$, \begin{align} &\log\left(\frac{n^k}{k!}\right)-\log\left(\frac{n^n}{n!}\right)\\ &=\log\left(\frac{n-0}{n}\right)+\log\left(\frac{n-1}{n}\right)+\cdots+\log\left(\frac{n-(n-k-1)}{n}\right)\\ &=\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right)\tag{1a} \end{align} and, bounding a Riemann Sum by integrals, $$\int_0^{\frac{n-k}n}\log(1-t)\,\mathrm{d}t \le\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right)\frac1n \le\int_0^{\frac{n-k-1}n}\log(1-t)\,\mathrm{d}t\tag{1b}$$ For $x\in[0,1]$, $-\frac12x^2-\frac12x^3\le\int_0^x\log(1-t)\,\mathrm{d}t\le-\frac12x^2$. Thus, $$-\frac12\left(\frac{n-k}{\sqrt{n}}\right)^2-\frac1{2\sqrt{n}}\left(\frac{n-k}{\sqrt{n}}\right)^3 \le\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right) \le-\frac12\left(\frac{n-k-1}{\sqrt{n}}\right)^2\tag{1c}$$ Exponentiating and dividing by $\sqrt{n}$ gives $$\exp\left(\scriptsize{-\frac12\left(\frac{n-k}{\sqrt{n}}\right)^2-\frac1{2\sqrt{n}}\left(\frac{n-k}{\sqrt{n}}\right)^3}\right)\frac1{\sqrt{n}} \le\frac{n^k}{k!}\frac{n!}{n^n}\frac1{\sqrt{n}} \le\exp\left(\scriptsize{-\frac12\left(\frac{n-k-1}{\sqrt{n}}\right)^2}\right)\frac1{\sqrt{n}}\tag{1d}$$ Summing over $k\in[0,n-1]$ and applying the Squeeze Theorem as $n\to\infty$ yields $$\lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=0}^{n-1}\frac{n^k}{k!} =\int_0^\infty e^{-t^2/2}\,\mathrm{d}t\tag{1e}$$

For $k\ge n$, \begin{align} &\log\left(\frac{n^k}{k!}\right)-\log\left(\frac{n^n}{n!}\right)\\ &=\log\left(\frac{n}{n+1}\right)+\log\left(\frac{n}{n+2}\right)+\cdots+\log\left(\frac{n}{n+(k-n)}\right)\\ &=-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right)\tag{2a} \end{align} and, bounding a Riemann Sum by integrals, $$-\int_0^{\frac{k-n+1}n}\log(1+t)\,\mathrm{d}t \le-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right)\frac1n \le-\int_0^{\frac{k-n}n}\log(1+t)\,\mathrm{d}t\tag{2b}$$ For $x\in[0,1]$, $-\frac12x^2\le-\int_0^x\log(1+t)\,\mathrm{d}t\le-\frac12x^2+\frac16x^3$. Thus, $$-\frac12\left(\frac{k-n+1}{\sqrt{n}}\right)^2 \le-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right) \le-\frac12\left(\frac{k-n}{\sqrt{n}}\right)^2+\frac1{6\sqrt{n}}\left(\frac{k-n}{\sqrt{n}}\right)^3\tag{2c}$$ Exponentiating and dividing by $\sqrt{n}$ yields $$\exp\left(\scriptsize{-\frac12\left(\frac{k-n+1}{\sqrt{n}}\right)^2}\right)\frac1{\sqrt{n}} \le\frac{n^k}{k!}\frac{n!}{n^n}\frac1{\sqrt{n}} \le\exp\left(\scriptsize{-\frac12\left(\frac{k-n}{\sqrt{n}}\right)^2+\frac1{6\sqrt{n}}\left(\frac{k-n}{\sqrt{n}}\right)^3}\right)\frac1{\sqrt{n}}\tag{2d}$$ Summing over $k\in[n,2n]$ and applying the Squeeze Theorem as $n\to\infty$ yields $$\lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=n}^{2n}\frac{n^k}{k!} =\int_0^\infty e^{-t^2/2}\,\mathrm{d}t\tag{2e}$$

For $t\ge1$, $\log\left(\frac1{1+t}\right)\le-\log(2)$. Using this and $(2b)$, we get, for $k\ge2n$, \begin{align} -\sum_{j=1}^{k-n}\log\left(1+\frac jn\right) &\le-\sum_{j=1}^n\log\left(1+\frac jn\right) -\sum_{j=n+1}^{k-n}\log(2)\\ &\le(1-2\log(2))n-\log(2)(k-2n)\tag{3a} \end{align} Thus, for $k\ge2n$, $$\frac{n^k}{k!}\le\frac{n^n}{n!}\left(\frac e4\right)^n2^{-(k-2n)}\tag{3b}$$ Therefore, $$\lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k\gt2n}\frac{n^k}{k!} \le\lim_{n\to\infty}\frac1{\sqrt{n}}\left(\frac e4\right)^n =0\tag{3c}$$

Combining $\text{(1e)}$, $\text{(2e)}$, and $\text{(3c)}$, we get \begin{align} \lim_{n\to\infty}\frac{n!}{n^n}\frac{e^n}{\sqrt{n}} &=\lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=0}^\infty\frac{n^k}{k!}\\ &=2\int_0^\infty e^{-x^2/2}\,\mathrm{d}x\\[9pt] &=\sqrt{2\pi}\tag4 \end{align}