# Show that the following holds;

Let $h(p) = -p \log p-(1-p)\log (1-p)$ denote the binary entropy of a Bernoulli distribution when the probability of observing a zero is $p$, where $\log$ denotes the logarithm to base 2. Show, using Stirling's approximation:

$$\ln(n!) = (n+\frac{1}{2})\ln(n) - n + O(1)$$

that the following holds:

$$\log\binom{n}{\gamma n} = nh(\gamma) -\frac{1}{2} \log n + O(1).$$

How should I do this?

$$\log{\binom n{\gamma n}} = \log{\frac{n!}{(n-\gamma n)!(\gamma n)!}}\\ = \left(n+\frac 12\right)\log n - n - \left(n\gamma +\frac 12\right)\log \gamma n + \gamma n \\- \left(n - n\gamma +\frac 12\right)\log (n - \gamma n) + (n - \gamma n) + O(1) \\= n\log n - (n - n\gamma)\log (n - \gamma n) - (n\gamma )\log \gamma n + \frac 12\log n - \frac 12(\log n + \log(1-\gamma)) - \frac 12(\log n + \log \gamma) + O(1)\\= n(\log n - (1-\gamma)\log (n - \gamma n)- \gamma \log \gamma n) -\frac 12\log n + O(1) \\= n\left( - (1-\gamma)\log \frac{n - \gamma n}n - \gamma \log \frac{\gamma n}n \right) -\frac 12\log n + O(1) = nh(\gamma) +\frac 12 \log n + O(1)$$