Skip to content

Bounds On Binomial Coefficents

January 15, 2014
tags: , , , , ,


A simple but useful bound on binomial coefficients

Unknown

Andreas von Ettingshausen was a German mathematician and physicist who lived in the early part of the 19{^{th}} century. He studied philosophy and jurisprudence, but later taught and wrote exclusively on mathematics and physics. Something that today, a mere 200 years later, would be impossible.

Today I wish to share a simple inequality with you on binomial coefficients.

This issue arose in a proof I am working on that concerns a new approach to circuit lower bounds. That is still in progress, could easily fail, but I thought this simple result would be of some interest.

The bound on binomial coefficients made me think about the related issue of who created the beautiful notation for them:

\displaystyle { n \choose k}.

The answer—you may already have guessed—is that von Ettingshausen did. Binomial numbers were known long before his work. Pascal’s triangle was known for centuries already in Europe, and had been discovered even earlier by the tenth century in India. Earlier notation included some ugly ones like:

\displaystyle C(n,k), \ {}^{n}C_{k}, \ {}_{n}C_{k}, \ C^{k}_{n}, \ C_{n,k}.

I especially find terms like {{}^{n}C_{k}} unpleasing—the superscript {{}^{n}} just hangs there in space. So thank you, Herr Prof. Dr. von Ettingshausen.

Binomial Coefficients

Recall that

\displaystyle {n \choose k}

is the number of ways of choosing {k} things from {n} objects, where order does not matter. In many proofs it is quite useful to have approximate results for binomials. For example, the central-term for {n} even,

\displaystyle {n \choose n/2}

is well known to be approximately

\displaystyle \frac{2^{n}\sqrt{2}}{\sqrt{\pi n}}.

However, I need bounds on binomials where {k} is much smaller than {n}. In this case it is also well known that

\displaystyle {n \choose k} \approx \frac{n^{k}}{k!}.

The trouble with this is that I needed control on the exact errors. So I will sketch a proof of a bound that works well when {k} is small. For {k \le \sqrt{n}}:

\displaystyle \frac{n^{k}}{k!} \ge {n \choose k} \ge \frac{n^{k}}{4 \ k!}.

Binomial Inequalities

We need the following simple inequalities for the binomial coefficent that holds for {k \le \sqrt{n}}:

\displaystyle \frac{n^{k}}{k!} \ge {n \choose k} \ge \frac{n^{k}}{4 \ k!}.

The upper bound holds for all {k} and the lower bound requires the limit on the size of {k}. Note, that a much weaker lower bound is often given,

\displaystyle {n \choose k} \ge \frac{n^{k}}{k^{k}}.

This holds for all {k}, but is exponentially weaker when {k} is smaller that the square root of {n}. This is the primary reason for this work.

Here is the proof. We note that

\displaystyle \begin{array}{rcl} {n \choose k } &=& \frac{n(n-1)\cdots (n-(k-1))}{k!} \\ &=& \frac{n^{k}}{k!} \ (1-\frac{1}{n})\cdots(1- \frac{k-1}{n}) \\ &\ge& \frac{n^{k}}{k!} \ \left(1- \frac{k-1}{n} \right)^{k-1}. \end{array}

The upper bound {n^k/k!} is immediately clear from this—note that it too is best for small {k}. For the lower bound, consider the function {f(x,y)} equal to

\displaystyle \left(1-\frac{x}{n} \right)^{y}.

For {x} in {[1,n]} the function decreases as {x} increases; and for {x} in the same range, the function decreases as {y \ge 1} increases.

Therefore,

\displaystyle \left(1- \frac{k-1}{n} \right)^{k-1} \ge \left(1-\frac{1}{\sqrt n} \right)^{\sqrt n}

by our above remark. But we know that for all {t \ge 2},

\displaystyle (1 - \frac{1}{t})^{t} \ge 1/4.

Putting this all together shows that the inequality claimed is true. We can improve the constant {1/4} by limiting {n} to be large enough, but the above is sufficient for our needs. For an example,

\displaystyle \binom{100}{10} \approx 17.31 \times 10^{12}, \quad\text{while}\quad \frac{100^{10}}{4\cdot 10!} \approx 6.89 \times 10^{12}.

Open Problems

Is this result well known to you all? I found it out of necessity. Even though it is coarse, the fact that it is an inequality and not an asymptotic result is useful in some proofs. Sometimes we just need to have a convenient inequality.

from → History, People
15 Comments leave one →
  1. Anon permalink
    January 15, 2014 9:50 pm

    “He studied philosophy and jurisprudence, but later taught and wrote exclusively on mathematics and physics. Something that today, a mere 200 years later, would be impossible.”

    I disagree. Ed Witten studied history and linguistics before becoming a top physicist and mathematician 🙂

    Reply
    • KWRegan permalink
      January 16, 2014 1:59 pm

      I did not know that! We thought of mentioning Alexander McCall Smith, who besides his novels and children’s books is Professor of Medical Law (emeritus) at U.Edinburgh and wrote what remains the only digest of Botswana’s criminal code, besides co-founding the country’s opera training center.

      Reply
    • John Sidles permalink
      January 16, 2014 3:32 pm

      Andreas von Ettingshausen … studied philosophy and jurisprudence, but later taught and wrote exclusively on mathematics and physics. Something that today, a mere 200 years later, would be impossible.

      Also in the 19th century, Hermann von Helmholtz was both a practicing physician and an eminent mathematician/physicist.

      It is surprising and regrettable too — perhaps even shocking? — that during the 20th century there were (to the best of my knowledge) no MacTutor-level mathematician/physicians … unlike every previous century since the Islamic Golden Age (of Rhazes for example).

      A modest hope  Perhaps the 21st century will witness a return to the broadly Enlightened traditions of earlier centuries.

      Reply
  2. B. permalink
    January 16, 2014 3:07 am

    For many French mathematicians, the notation $C_n^k$ is the French notation while $\binom{n}{k}$ is the American one. As you can imagine, some (should I say old?) teachers in France were upsets when the new curriculum replaced the French notation by the American one… I think the American notation is now totally accepted, and this is a good thing to my mind since, as you mention, it is much nicer!

    Reply
  3. mskmoorthy permalink
    January 17, 2014 10:54 am

    Can 1/4 be replaced by 1/e to get a better bound?

    Reply
  4. Aryeh Kontorovich permalink
    January 18, 2014 2:37 pm

    Some binomial sum bounds can be surprisingly tricky — I humbly submit Lemma 5 here as an example.

    Reply
  5. William Gasarch permalink
    January 18, 2014 6:16 pm

    The results amazes me. I always thought that the approx (n choose k) is approx n^k/k!
    was somewhat crude since it seems as though you are tossing out so much information.
    Thanks much!

    Reply
  6. Radu Grigore permalink
    February 13, 2014 9:17 am

    I think ${n \choose k} \le \frac{1}{2}\frac{n^k}{k!}$ when $k\le\sqrt{n}$.

    Consider a hashtable with $n$ buckets and $k$ items. There are $n^k$ ways to distribute the items, out of which ${n \choose k}k!$ have no collision. The probability of having some collision is $1 – {n \choose k}k!/n^k$. Now suppose $Y$ is a random variable whose value says how many collisions there are. So,

    $$P(Y\gt 0)=1-\frac{{n \choose k}}{n^k/k!} \le {\rm E} Y$$

    The inequality comes from the first moment principle. The expected number of collisions increases with $k$, so we just look at the case $k=\sqrt{n}$. There are $\sqrt{n}(\sqrt{n}-1)/2$ possible collisions, each hapenning with probability $1/n$. Thus,

    $${\rm E}Y=\frac{\sqrt{n}(\sqrt{n}-1)}{2}\frac{1}{n}=\frac{1}{2}-\frac{1}{2\sqrt{n}}$$

    Putting the previous displayed inequalities together, we get

    $$1-\frac{{n \choose k}}{n^k/k!}\le\frac{1}{2}-\frac{1}{2\sqrt{n}}$$

    and finally

    $$\frac{{n \choose k}}{n^k/k!} \ge \frac{1}{2}+\frac{1}{2\sqrt{n}} \gt \frac{1}{2}$$

    Reply
    • Radu Grigore permalink
      February 13, 2014 9:25 am

      Trying to get LaTeX to work. I really hope this work, because I don’t know how to remove comments. Sorry.

      I think {n \choose k} \geq \frac{1}{2}\frac{n^k}{k!} when k\leq\sqrt{n}.

      Consider a hashtable with n buckets and k items. There are n^k ways to distribute the items, out of which {\binom{n}{k}}k! have no collision. The probability of having some collision is 1 - {\binom{n}{k}}k!/n^k. Now suppose Y is a random variable whose value says how many collisions there are. So,

      \displaystyle {P(Y > 0)=1-\frac{\binom{n}{k}}{n^k/k!} \leq {\rm E} Y}

      The inequality comes from the first moment principle. The expected number of collisions increases with k, so we just look at the case k=\sqrt{n}. There are \sqrt{n}(\sqrt{n}-1)/2 possible collisions, each happening with probability 1/n. Thus,

      \displaystyle {\rm E}Y=\frac{\sqrt{n}(\sqrt{n}-1)}{2}\frac{1}{n}=\frac{1}{2}-\frac{1}{2\sqrt{n}}

      Putting the previous displayed inequalities together, we get

      \displaystyle 1-\frac{\binom{n}{k}}{n^k/k!}\le\frac{1}{2}-\frac{1}{2\sqrt{n}}

      and finally

      \displaystyle {\frac{\binom{n}{k}}{n^k/k!} \geq \frac{1}{2}+\frac{1}{2\sqrt{n}} > \frac{1}{2}}

      Reply
      • Pip permalink
        February 13, 2014 3:09 pm

        I fixed the parse errors, though I don’t understand how or why, and also the inequality direction you note below. I can say this since both of me are in my office now.

      • Thomas Dybdahl Ahle permalink
        September 4, 2015 2:52 am

        This looks good to me. I like the use of the moment method.
        [x]

    • Radu Grigore permalink
      February 13, 2014 9:31 am

      Oh, dear: The very first inequality goes the wrong way. I meant that {n \choose k}\ge\frac{1}{2} when $k\le\sqrt{n}$. (The rest seems OK, appart from the formulas that aren’t parsed and appear just in the latex version.)

      Reply
  7. Thomas Dybdahl Ahle permalink
    September 4, 2015 4:41 am

    We can also use the simple lower bound $\product_{i=1}^{k-1} 1-i/n\ge e^{-k^2/n}$, though it doesn’t give quite as good a bound as Radu Grigore’s.

    Reply
    • Thomas Dybdahl Ahle permalink
      September 4, 2015 4:50 am

      \product_{i=1}^{k-1} 1-i/n\ge e^{-k^2/n} that is.

      Reply
    • Thomas Dybdahl Ahle permalink
      September 4, 2015 4:51 am

      \prod_{i=1}^{k-1} 1-i/n\ge e^{-k^2/n}

      Reply

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading