Stirling's approximation

From TCS Wiki
Revision as of 03:05, 11 September 2010 by 127.0.0.1 (talk) (Created page with '== 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>n!<…')
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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]