# Thread: Stirling's approximation to estimate n choose m

1. ## 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...

2. 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)$)

,

,

### n choose k stirling

Click on a term to search for related topics.