Bounds On Binomial Coefficents
A simple but useful bound on binomial coefficients
Andreas von Ettingshausen was a German mathematician and physicist who lived in the early part of the 19 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:
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:
I especially find terms like unpleasing—the superscript just hangs there in space. So thank you, Herr Prof. Dr. von Ettingshausen.
is the number of ways of choosing things from 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 even,
is well known to be approximately
However, I need bounds on binomials where is much smaller than . In this case it is also well known that
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 is small. For :
We need the following simple inequalities for the binomial coefficent that holds for :
The upper bound holds for all and the lower bound requires the limit on the size of . Note, that a much weaker lower bound is often given,
This holds for all , but is exponentially weaker when is smaller that the square root of . This is the primary reason for this work.
Here is the proof. We note that
The upper bound is immediately clear from this—note that it too is best for small . For the lower bound, consider the function equal to
For in the function decreases as increases; and for in the same range, the function decreases as increases.
by our above remark. But we know that for all ,
Putting this all together shows that the inequality claimed is true. We can improve the constant by limiting to be large enough, but the above is sufficient for our needs. For an example,
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.