6
$\begingroup$

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!}$$

I found this reference to using the binary entropy function and Stirling's approximation.

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ May 1, 2017 at 14:37

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Jun 24, 2022 at 2:02
  • $\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
    Jan 6 at 3:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .