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.

  • 2
    $\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$ – Jack D'Aurizio May 1 '17 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.