9

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?

Wadim Zudilin
  • 13,404
Carla
  • 91
  • 1
    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 http://mathoverflow.net/questions/27912/. – Wadim Zudilin Jul 26 '10 at 09: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 09: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
  • The AGM inequality gives some trivial lower bound, not so? – Sergei Jun 28 '15 at 09:11
  • OP asked for a lower bound for the partial sum, and it's never answered directly. I don't have an answer either, but realize that it might be helpful to look into Hypergeometric Distribution. In particular, an upper bound of the tail is given in the link. However, no lower bound yet has been given. One has to turn to finer analysis of hypergeometric distributions. Hopefully someone can make this answer complete. ((also related: https://mathoverflow.net/questions/357560/local-behavior-of-the-vandermonde-convolution)). – Student Apr 16 '20 at 15:19

1 Answers1

6

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.

Wadim Zudilin
  • 13,404
  • 1
    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
  • 1
    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