Welcome to MathOverflow

Question

2

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?

edited Jul 26 2010 at 10:58

Wadim Zudilin
8,674●1●24●59

asked Jul 26 2010 at 8:57

Carla
21●2

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 mathoverflow.net/questions/27912. – Wadim Zudilin Jul 26 2010 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 2010 at 9:35

Wadim, computing asymptotics of "interesting" combinatorial expressions is surely part of combinatorics! – JBL Jul 26 2010 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 2010 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 2010 at 13:34

Wadim Zudilin · Accepted Answer · 2010-07-26 10:52:18Z UTC

4

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.

answered Jul 26 2010 at 10:52

Wadim Zudilin

community wiki

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 2010 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 2010 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 2010 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 2010 at 22:10

Partial sums of the Chu--Vandermonde identity

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.