Best upper and lower bound for a binomial coefficient

Question

I was reading a blog entry which suggests the following upper and lower bound for a binomial coefficient:

$$\left(\frac{n}{k}\right)^k \le {n \choose k} \le \left(\frac{en}{k}\right)^k$$

I found an excellent explanation of the proof here.

From this article, if $k < \sqrt{n}$:

$$\frac{n^k}{4(k!)} \le {n \choose k}\le \frac{n^k}{k!}$$

Are these the best known upper and lower bounds? Are there any other well known tighter upper and lower bounds available?

Would I be correct in assuming that Stirling's Approximation leads to the tightest upper and lower bound?

Edit: Added 1 more inequality that I hadn't seen before with the source.

If $n$ is large enough, the binomial distribution is well-approximated by a normal distribution, hence you may use the central limit theorem and the Berry-Esseen theorem (en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem) to improve such inequalities. — Jack D'Aurizio, Commented May 1, 2017 at 14:37

Max · Accepted Answer · 2020-02-09 13:37:31Z

5

For the special case $n = 2k$, we can get narrower bounds:

$$\frac{1}{2k} 2^{2k} \leq \binom{2k}{k} \leq 2^{2k}$$

The proof is given as an exercise in Robert J. Vanderbei, Linear Programming: Foundations and Extensions, ch. 4.

answered Feb 9, 2020 at 13:37

Max

1,2779 silver badges24 bronze badges

1

$\begingroup$ Just in-case the reader did not click the Stirling approximation link... The upper-bound can be improved to $\frac{2^{2k}}{\sqrt{k}}$ (actually $\frac{2^{2k}}{\sqrt{\pi k}}$, but that's not as easy to remember). $\endgroup$
– Xin Yuan Li
Commented Jun 24, 2022 at 2:02
1

$\begingroup$ Classical result is $\displaystyle\frac{4^n}{\sqrt{\pi(n+\frac{1}{2})}}<\binom{2n}{n}<\frac{4^n}{\sqrt{\pi n}}$ derived from computing and estimating Wallis integrals $\displaystyle W_n=\int_0^{\pi/2}\cos^n(x)dx$. For even and odd cases: $\displaystyle W_{2n}=\frac{\binom{2n}{n}}{4^n}\frac{\pi}{2}; W_{2n+1}=\frac{4^n}{(2n+1)\binom{2n}{n}}$ then using recurrent relation $nW_n=(n-1)W_{n-2}$ where $(W_0=\pi/2, W_1=1)$ and integrals estimation $W_{2n+1}<W_{2n}<W_{2n-1}=\frac{2n+1}{2n}W_{2n+1}$, one can deduce both the limits. $\endgroup$
– Van Jone
Commented Jan 6 at 3:25

Add a comment |

1 Answer 1