Asymptotics of binomial coefficients and the entropy function
I found a question while I was trying to practice Combinatorics and Probabilistic methods.I tried to solve it with no success.. this is the question:
Use the Stirling approximation of the factorial to show that for every $0\leq p \leq 1$ there holds
$$\lim _{n\to \infty}\frac{1}{n}\log\binom{n}{pn}=H(p)$$ where $H(p)=-p\log(p) -(1-p)\log(1-p)$ is the binary entropy function.
Any help?
Let $q=1-p$.
The Stirling approximation asserts $n! \sim (\frac{n}{e})^{n} \sqrt{2\pi n}$. This gives:
$$\binom{n}{pn} \sim \frac{(n/e)^{n}}{(np/e)^{np}(nq/e)^{nq}}\frac{\sqrt{2\pi n}}{\sqrt{2\pi np}\sqrt{2\pi nq}}$$
The $(n/e)^n$ cancels with $(n/e)^{np}(n/e)^{nq}$, so this simplifies to:
$$\binom{n}{pn} \sim \frac{1}{p^{np}q^{nq}}\frac{1}{\sqrt{2\pi npq}}$$ Upon taking logarithm in base 2, we get:
$$\log_2\binom{n}{pn} \sim -n (p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/2$$ Dividing by $n$, it transforms to:
$$\frac{1}{n}\log_2\binom{n}{pn} \sim -(p\log_2 p + q \log_2 q) - \log_2 (2\pi n pq)/(2n) = H(p) + O(\ln n/ n)$$ And when $n$ tends to infinity, we get the desired limit.
EDIT: You don't need the full strength of Stirling approximation. $n! = (n/e)^{n} g(n)$ where $n^{\alpha} \le g \le n^{\beta}$ is enough.