Show that $G\left(n,p\right)e^{-\frac{1}{12np\left(1-p\right)}}<{n\choose pn} < G\left(n, p\right)$

Question

The problem:

Using the inequalities

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}e^{\left(\frac{1}{12n}-\frac{1}{360n^{3}}\right)} < n! < \sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{\frac{1}{12n}}$

show that, for a constant $p$ such that $0<p<1$, where $pn$ is an integer,

$G\left(n, p\right)=\frac{2^{nH\left(p\right)}}{\sqrt{2\pi n p\left(1-p\right)}}$, and $H\left(p\right)$ is the binary entropy function, show that

$G\left(n,p\right)e^{-\frac{1}{12np\left(1-p\right)}}<{n\choose pn} < G\left(n, p\right)$

My work so far:

First I have noted that

${n\choose pn} = \frac{n!}{\left(pn\right)!\left(\left(1-p\right)n\right)!}$

$ \approx \frac{\sqrt{2\pi n} \left( \frac{n}{e} \right)^{n}}{\left(pn\right)!\left(\left(1-p\right)n\right)!}$

$\approx \frac{ \sqrt{2\pi \left(1-p\right)n}\left( \frac{\left(1-p\right)n}{e}\right)^{\left(1-p\right)n}}{2\pi \sqrt{\left(1-2p\right)}\left(\frac{pn}{e}\right)^{pn} \left(\frac{\left(1-2p\right)n}{e}\right)^{\left(1-2p\right)n}} e^\left({\frac{1}{12\left(1-p\right)n}}-\frac{1}{12pn+1}-\frac{1}{12\left(1-2p\right)n+1}\right)$

$\leq 2^{nH\left(p\right)} \frac{e^{\frac{1}{12n}}}{\sqrt{2\pi np\left(1-p\right)}}$

and from here I am not sure where to go. Any hints or help would be greatly appreciated.

Answer 1

I put $q=1-p$. First, I shall use the inequalities $$ \sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n < n! < \sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n e^{\frac{1}{{12n}}} $$ which hold for all positive integer $n$. We obtain $$ \binom{n}{pn} > \frac{{\sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n }}{{\sqrt {2\pi pn} \left( {\frac{{pn}}{e}} \right)^{pn} e^{\frac{1}{{12pn}}} \sqrt {2\pi qn} \left( {\frac{{qn}}{e}} \right)^{qn} e^{\frac{1}{{12qn}}} }} = \frac{{2^{nH(p)} }}{{\sqrt {2\pi pqn} }}e^{ - \frac{1}{{12npq}}} . $$ To prove the upper bound, I shall use the inequalities $$ \sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n e^{\frac{1}{{12n+1}}} < n! < \sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n e^{\frac{1}{{12n}}} $$ which hold for all positive integer $n$ (cf. H. Robbins, A remark on Stirling's formula, Amer. Math. Monthly 62 (1955), pp. 26–29.). We deduce $$ \binom{n}{pn} < \frac{{\sqrt {2\pi n} \left( {\frac{n}{e}} \right)^n e^{\frac{1}{{12n}}} }}{{\sqrt {2\pi pn} \left( {\frac{{pn}}{e}} \right)^{pn} e^{\frac{1}{{12np + 1}}}\sqrt {2\pi qn} \left( {\frac{{qn}}{e}} \right)^{qn} e^{\frac{1}{{12nq + 1}}}}} = \frac{{2^{nH(p)} }}{{\sqrt {2\pi pqn} }}e^{\frac{1}{{12n}} - \frac{1}{{12np + 1}} - \frac{1}{{12nq + 1}}} . $$ Finally, note that $$ \frac{1}{{12n}} - \frac{1}{{12pn + 1}} - \frac{1}{{12qn + 1}} = - \frac{{144n^2 (pq + 1) + 12n - 1}}{{12n(12np + 1)(12nq + 1)}} < 0. $$

Answer 2

In inequality $\text{(4d)}$ of this answer, it is shown that $$ \frac1{12n+1}\le\log\left(\frac{n!\,e^n}{\sqrt{2\pi n}\,n^n}\right)\le\frac1{12n}\tag1 $$ Assuming that $$ H(p)=-p\log_2(p)-(1-p)\log_2(1-p)\tag2 $$ and using $$ G(n,p)=\frac{2^{nH(p)}}{\sqrt{2\pi np(1-p)}}\tag3 $$ $(1)$ implies $$ \scriptsize\frac1{12}\overbrace{\left[\frac1{n+\frac1{12}}-\frac1{np}-\frac1{n(1-p)}\right]}^{\large\frac1{n+1/12}-\frac1{np(1-p)}} \le\log\left(\frac1{G(n,p)}\binom{n}{pn}\right) \le\frac1{12}\overbrace{\left[\frac1{n}-\frac1{np+\frac1{12}}-\frac1{n(1-p)+\frac1{12}}\right]}^{\large\le\frac1n-\frac1{p(1-p)(n-1/6)+1/12}}\tag4 $$ Note that the upper bound is negative when $n\ge1$ since $0\le p(1-p)\le\frac14$.

Therefore, $$ e^{\frac1{n+1/12}-\frac1{np(1-p)}}\le\frac1{G(n,p)}\binom{n}{pn}\le e^{\frac1n-\frac1{p(1-p)(n-1/6)+1/12}}\tag5 $$ which is stronger than the requested inequality.