Stirling's approximation

In mathematics, Stirling's approximation (or Stirling's formula) is an asymptotic approximation for factorials. It is a good approximation, leading to accurate results even for small values of ${\displaystyle n}$. It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.

One way of stating the approximation involves the logarithm of the factorial: $${\displaystyle \ln n!=n\ln n-n+O(\ln n),}$$ where the big O notation means that, for all sufficiently large values of ${\displaystyle n}$, the difference between ${\displaystyle \ln n!}$ and ${\displaystyle n\ln n-n}$ will be at most proportional to the logarithm of ${\displaystyle n}$. In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to instead use the binary logarithm, giving the equivalent form $${\displaystyle \log _{2}n!=n\log _{2}n-n\log _{2}e+O(\log _{2}n).}$$ The error term in either base can be expressed more precisely as ${\displaystyle {\tfrac {1}{2}}\log 2\pi n+O({\tfrac {1}{n}})}$, corresponding to an approximate formula for the factorial itself, $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.}$$ Here the sign ${\displaystyle \sim }$ means that the two quantities are asymptotic, that is, their ratio tends to 1 as ${\displaystyle n}$ tends to infinity.

The formula was first discovered by Abraham de Moivre in 1721 in the form $${\displaystyle n!\sim [{\rm {constant}}]\cdot n^{n+{\frac {1}{2}}}e^{-n}.}$$

De Moivre gave an approximate rational-number expression for the natural logarithm of the constant. Stirling's contribution in 1730 consisted of showing that the constant is precisely ${\displaystyle {\sqrt {2\pi }}}$.

Roughly speaking, the simplest version of Stirling's formula can be quickly obtained by approximating the sum $${\displaystyle \ln n!=\sum _{j=1}^{n}\ln j}$$ with an integral: $${\displaystyle \sum _{j=1}^{n}\ln j\approx \int _{1}^{n}\ln x\,{\rm {d}}x=n\ln n-n+1.}$$

The full formula, together with precise estimates of its error, can be derived as follows. Instead of approximating ${\displaystyle n!}$, one considers its natural logarithm, as this is a slowly varying function: $${\displaystyle \ln n!=\ln 1+\ln 2+\cdots +\ln n.}$$

The right-hand side of this equation minus $${\displaystyle {\tfrac {1}{2}}(\ln 1+\ln n)={\tfrac {1}{2}}\ln n}$$ is the approximation by the trapezoid rule of the integral $${\displaystyle \ln n!-{\tfrac {1}{2}}\ln n\approx \int _{1}^{n}\ln x\,{\rm {d}}x=n\ln n-n+1,}$$

and the error in this approximation is given by the Euler–Maclaurin formula: $${\displaystyle {\begin{aligned}\ln n!-{\tfrac {1}{2}}\ln n&=\ln 1+\ln 2+\ln 3+\cdots +\ln(n-1)+{\tfrac {1}{2}}\ln n\\&=n\ln n-n+1+\sum _{k=2}^{m}{\frac {(-1)^{k}B_{k}}{k(k-1)}}\left({\frac {1}{n^{k-1}}}-1\right)+R_{m,n},\end{aligned}}}$$