# Are there good bounds on binomial coefficients?

Motivated by the central limit theorem, one expects that $$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right).$$ Computations suggest that the ratio of the two sides approaches 1 only for $|k-n/2| < 2\sqrt{n}$, and presumably this will follow from some version of the CLT.

In the literature or standard usage, are there any explicit upper (and lower?) bounds for binomial coefficients with a similar form that are sharp (in the ratio sense) for a wider range of $k$?

• How about using Stirling's approximation to factorial when k is a significant fraction of n? Gerhard "How Good Is Good Really?" Paseman, 2016.04.17. Apr 18 '16 at 4:26
• So using Stirling's formula, you get an approximation to within a (small) constant simultaneously valid for all $n$ and $k$. Apr 18 '16 at 4:41
• Stirling's formula is indeed awesome, but it leaves one with $k^k$ and $(n-k)^{n-k}$ factors which are too cumbersome to work with in my application. Apr 19 '16 at 1:15
• Can you say more about your application? It seems like the kind of bound you want depends a lot on how you're using it. (And for instance if you care about sums of binomial coefficients, this may not be the best approach.)
– usul
Apr 19 '16 at 1:48
Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have $$\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}$$ where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.
• See this: eudml.org/doc/121842. Stanica's paper even improves the lower bound to $1-1/(32n)$ times the upper bound given by kodlu. Apr 18 '16 at 18:42
• Shouldn't the minus signs in the exponents be removed? As it is, it looks like for say $k=\frac{n}{2}$ both upper and lower bound go to $0$. Apr 18 '16 at 19:34
• This inequality can be written in a simpler way without using the entropy function: since $n h (k/n) = k \ln(n/k) + (n-k)\ln(n/(n-k))$, $\exp(\cdot) = (n/k)^k\cdot (n/(n-k))^{n-k} = {n^n \over k^k (n-k)^{n-k}}$, so both the upper and the lower bounds are constant multiples of ${n^{n+1/2} \over k^{k+1/2} (n-k)^{n-k+1/2}}$. Sep 19 '18 at 20:45