9
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 26, 2010 at 9:16
  • $\begingroup$ 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) $\endgroup$ Jul 26, 2010 at 9:35
  • $\begingroup$ Wadim, computing asymptotics of "interesting" combinatorial expressions is surely part of combinatorics! $\endgroup$
    – JBL
    Jul 26, 2010 at 11:30
  • $\begingroup$ @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. $\endgroup$ Jul 26, 2010 at 12:38
  • $\begingroup$ 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$. $\endgroup$
    – JBL
    Jul 26, 2010 at 13:34

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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... $\endgroup$ Jul 26, 2010 at 11:46
  • 1
    $\begingroup$ 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^*}$. $\endgroup$ Jul 26, 2010 at 12:35
  • $\begingroup$ 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$.) $\endgroup$
    – Carla
    Jul 27, 2010 at 14:27
  • $\begingroup$ 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... $\endgroup$ Jul 27, 2010 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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