# Stirling's approximation to estimate n choose m

• Nov 26th 2009, 01:25 AM
Boysilver
Stirling's approximation to estimate n choose m
Let $m$ be an integer with $m/m = p + o(1)$ for $0 < p < 1$. Show ${n\choose{m}} = 2^{n(H+o(1))}$ where $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 $m$ be an integer with $m/n = p + o(1)$ for $0 < p < 1$. Show ${n\choose{m}} = 2^{n(H+o(1))}$ where $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: $\log (n!)=k\log k-k+o(k)$ (log in base e).

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