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]