Stirling's approximation

Stirling's Approximation

As we have seen, answers to many counting problems are expressed in terms of factorials. It is important for us to know roughly how large [math]\displaystyle{ n! }[/math] is, i.e. the asymptotic order of [math]\displaystyle{ n! }[/math]. This is done by the famous Stirling's approximation, also called Stirling's formula.

Theorem (Stirling's approximation)

[math]\displaystyle{ n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n }[/math].

The symbol [math]\displaystyle{ \sim\, }[/math] means that [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}=1 }[/math].

The proof of the Stirling's approximation is complicated. We will prove the following easier proposition.

Proposition

[math]\displaystyle{ \ln (n!)=n\ln n-n+O(\ln n)\, }[/math]

Proof. The logarithm of [math]\displaystyle{ n! }[/math] is [math]\displaystyle{ \ln (n!)=\sum_{k=1}^n\ln k }[/math]. Since [math]\displaystyle{ f(x)=\ln x }[/math] is an increasing function of [math]\displaystyle{ x }[/math] for all positive [math]\displaystyle{ x }[/math], we have [math]\displaystyle{ \ln (n!)=\sum_{k=1}^n\ln k \le \int_2^{n+1}\ln x\, \mathrm{d}x =(n+1)\ln(n+1)-(n+1)-2\ln 2+2. }[/math] Note that [math]\displaystyle{ \ln(n+1)-\ln n=\int_{n}^{n+1}\frac{1}{x}\,\mathrm{d}x\lt \frac{1}{n}, }[/math] thus [math]\displaystyle{ n\ln (n+1)\lt n\ln n+1 }[/math]. Combining this with the above upper bound, [math]\displaystyle{ \ln (n!)\le n\ln n-n+O(\ln n). }[/math] [math]\displaystyle{ \square }[/math]

The full proof of Stirling's approximation involves a more precise estimation of the constant factor in [math]\displaystyle{ O(\ln n) }[/math].

Binomial coefficient

For binomial coefficient, we can approximate it by the Stirling's approximation of factorial, but we also have an easier (but loose) estimation.

Proposition

[math]\displaystyle{ \left(\frac{n}{k}\right)^k\le {n\choose k} \lt \left(\frac{\mathrm{e}n}{k}\right)^k }[/math]

Proof. The lower bound is easy: [math]\displaystyle{ {n\choose k}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdots\frac{n-k+1}{1}\ge\frac{n}{k}\cdot\frac{n}{k}\cdots\frac{n}{k}=\left(\frac{n}{k}\right)^k }[/math]. For the upper bound, [math]\displaystyle{ \mathrm{e}^{nx}\gt (1+x)^n=\sum_{i=1}^n{n\choose i}x^i\gt {n\choose k}x^k, }[/math] for any [math]\displaystyle{ 0\le k\le n }[/math]. Setting [math]\displaystyle{ x=\frac{k}{n} }[/math], we have [math]\displaystyle{ \mathrm{e}^k\gt {n\choose k}\left(\frac{k}{n}\right)^k. }[/math] Therefore, [math]\displaystyle{ {n\choose k} \lt \left(\frac{\mathrm{e}n}{k}\right)^k }[/math]. [math]\displaystyle{ \square }[/math]