MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in finding a lower bound of the sum: $$\sum_{i=0}^d \left(\genfrac{}{}{0pt}{}{n}{i}\right) \left(\genfrac{}{}{0pt}{}{m}{k-i}\right)$$ when $d < k$ (and assuming both $n\geq k$, $m\geq k$). When $d=k$ this sum is equal to $$\left(\genfrac{}{}{0pt}{}{n+m}{k}\right) $$ (the Chu--Vandermonde identity). What I would like to know if there is some good and standard lower bound for the first $d$ terms of this sum in terms of the relation between $d$ and $k$. Is there some standard reference book where I can hope to find such a bound?

share|cite|improve this question
Your problem is not from "combinatorics": you ask for analytic (asymptotic) estimates for binomial coefficients. There is a book by de Brijn, "Asymptotic methods in analysis", which discuss this sort of problems; you may also have a look at – Wadim Zudilin Jul 26 '10 at 9:16
I'm not sure I understand: what's the "relaton between $d$ and $k$": do you mean the ratio $d/k$ ? (Fixed typo in the title) – Pietro Majer Jul 26 '10 at 9:35
Wadim, computing asymptotics of "interesting" combinatorial expressions is surely part of combinatorics! – JBL Jul 26 '10 at 11:30
@JBL: I would be happy to agree with you but I am not convinced that some part of a natural binomial sum is "interesting". Unless the author gives some combinatorial background for it. For the moment, there is no combinatorics in the OP. – Wadim Zudilin Jul 26 '10 at 12:38
The problem (essentially) asks for the probability that, when $k$ balls are selected at random from among $n + m$, at most $d$ of those selected come from the first $n$. – JBL Jul 26 '10 at 13:34
up vote 5 down vote accepted

Carla, I don't think it is a good idea to give a detailed solution here. My point is that this problem is pretty standard: if you look inside N.G. de Bruijn's Asymptotic Methods in Analysis, especially in the 3rd chapter, you will find that your sum (generically) falls into the category c (p. 54, a comparatively small number of terms somewhere in the middle); the method is discussed in full details (Section 3.4) on the example of a very similar binomial sum.

share|cite|improve this answer
Why it's not a good idea? Isn't there a way to give a few lines description, plus the reference? I don't think that should be off the scopes of this site. It's a standard problem, of course, but many specialists in several areas of maths are not supposed to know how to approach it. The detailed reference is worth a $+\lceil 1/2 \rceil$ however... – Pietro Majer Jul 26 '10 at 11:46
Pietro, you are probably right and some MO readers might be interested in seeing a solution. I would be happy however to give this opportunity to somebody else, better to Carla herself. The idea explained in the book is simple: you search for the index $i^*=i$ for which $a_{i+1}/a_i$ (which is rational in $i$) is approximately $1$; this gives the maximum (and dominating!) term in the sum $\sum_{i=0}^da_i$. Finally, one applies Stirling's formula to this single term $a_{i^*}$. – Wadim Zudilin Jul 26 '10 at 12:35
Thank you for the reference to de Brujin's book. Well, I was interested in a lower bound and the example you mention seems to be for an upper bound, right? I figured that the best way to find a lower bound of this sum is to find a lower bound of the following sum, which is less or equal to the original sum: $$(\sum_{i=0}^d \left(\genfrac{}{}{0pt}{}{n}{i}\right)) min_{i=0,\ldots,d} \left(\genfrac{}{}{0pt}{}{m}{k-i}\right).$$ Each term of the product can be easily bounded now (for the 1st term using for instance that $\sum_{i=0}^d \left(\genfrac{}{}{0pt}{}{n}{i}\right)) \leq (n+1)^d$.) – Carla Jul 27 '10 at 14:27
Carla, you were interested in* means that you are not any more. Your lower bound is definitely correct but not sharp; the one from the book gives you the asymptotic behaviour of your partial sums, that is, the bounds from above and from below at the same time. But of course you have to choose what are (were) real needs... – Wadim Zudilin Jul 27 '10 at 22:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.