# Stirling's approximation to estimate n choose m

• Nov 26th 2009, 01:25 AM
Boysilver
Stirling's approximation to estimate n choose m
Let $\displaystyle m$ be an integer with $\displaystyle m/m = p + o(1)$ for $\displaystyle 0 < p < 1$. Show $\displaystyle {n\choose{m}} = 2^{n(H+o(1))}$ where $\displaystyle H = -p \log p - (1-p) \log (1-p)$ where the logs are to the base 2.

I've tried using the binomial tail but can't get this to work...
• Nov 30th 2009, 02:25 PM
Laurent
Quote:

Originally Posted by Boysilver
Let $\displaystyle m$ be an integer with $\displaystyle m/n = p + o(1)$ for $\displaystyle 0 < p < 1$. Show $\displaystyle {n\choose{m}} = 2^{n(H+o(1))}$ where $\displaystyle H = -p \log p - (1-p) \log (1-p)$ where the logs are to the base 2.

I've tried using the binomial tail but can't get this to work...

This is a consequence of Stirling's approximation formula, in a weaker form: $\displaystyle \log (n!)=k\log k-k+o(k)$ (log in base e).

Write $\displaystyle {n\choose m}=\frac{n!}{m!(n-m)!}$, take logarithms, use $\displaystyle m=np+o(n)$ (hence $\displaystyle n-m= n(1-p)+o(n)$) and the above formula. After simplifications, you'll get your formula (i.e. $\displaystyle \frac{1}{\log 2}\log{n\choose m}=n H +o(n)$)