# Partial sums of the Chu--Vandermonde identity

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?

-
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 mathoverflow.net/questions/27912. – 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

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