# Prove a combinatorial identity involving summing product of binomial coefficients

I encountered the following two identities when solving a combinatorial problem. I am wondering whether these two identities can be proved directly without resorting to combinatorial arguments (or if there exists simple intuitive combinatorial arguments): $$\sum_{i=s}^{n+s-r}\frac{\binom{i-1}{s-1}\binom{n-i}{r-s}}{\binom{n}{r}}=1,$$ where $$1\leq s\leq r\leq n$$. In this way, $$P(i)=\binom{i-1}{s-1}\binom{n-i}{r-s}/\binom{n}{r}$$ defines a probability mass function (PMF), $$i=s,\ldots,n+s-r$$. This one looks like Vandermonde's identity.

The second identity involves the expectation of $$i$$ defined by the above PMF: $$\sum_{i=s}^{n+s-r}i\frac{\binom{i-1}{s-1}\binom{n-i}{r-s}}{\binom{n}{r}}=\frac{n+1}{r+1}s.$$

Any help or insight will be appreciated.

• After moving the denominator up onto the right hand side, and reindexing the sum, your first identity becomes the "upside-down Vandermonde convolution identity" (see, e.g., Theorem 1 in math.stackexchange.com/questions/2587436/… ). Commented Aug 18, 2019 at 18:41
• As for the second identity, note that $i\dbinom{i-1}{s-1} = s\dbinom{i}{s}$. Commented Aug 18, 2019 at 18:43
• Thank you for your comments! They actually solved all my problem.
– Tom
Commented Aug 18, 2019 at 18:53

$$\sum_{i=s}^{n+s-r}\frac{\binom{i-1}{s-1}\binom{n-i}{r-s}}{\binom{n}{r}}=\binom{n}{r}^{-1}\;\;\sum_{i=s}^{n+s-r}\binom{i-1}{i-s}\binom{n-i}{n-i-r+s}$$$$=\binom{n}{r}^{-1}\;\;\sum_{i=s}^{n+s-r}\left(-1\right)^{i-s}\binom{-s}{i-s}\left(-1\right)^{n-r+s-i}\binom{-r+s-1}{n-i-r+s}$$$$=\binom{n}{r}^{-1}\left(-1\right)^{n-r}\;\;\sum_{i=s}^{n+s-r}\binom{-s}{i-s}\binom{-r+s-1}{n-i-r+s}$$$$=\binom{n}{r}^{-1}\left(-1\right)^{n-r}\binom{-r-1}{n-r}=\binom{n}{r}^{-1}\binom{n}{n-r}=\binom{n}{r}^{-1}\binom{n}{r}=1$$

Hence we showed that:

$$\bbox[5px,border:2px solid #00A000]{\sum_{i=s}^{n+s-r}\frac{\binom{i-1}{s-1}\binom{n-i}{r-s}}{\binom{n}{r}}=1}$$

As desired.

For (1) you can turn the argument on its head.

If we are drawing balls (without replacement) from an urn containing $$n$$ balls out of which $$r$$ are marked, then consider the event that the $$i$$th draw results in the $$s$$th marked ball being drawn. This corresponds to the case when the previous $$(i-1)$$ draws have resulted in drawing of $$s-1$$ marked balls (the probability of which is hypergeometric and given by $$\frac{\binom{r}{s-1}\binom{n-r}{i-s}}{\binom{n}{x-1}}$$) and the case that the $$i$$th draw results in drawing of a marked ball (the probability of which is $$\frac{r-s+1}{n-i+1}$$ i.e. the proportion of marked balls left) and hence has the probability (in the classical sense) equal to $$\frac{\binom{r}{s-1}\binom{n-r}{i-s}}{\binom{n}{x-1}}\cdot \frac{r-s+1}{n-i+1}=\frac{\binom{i-1}{s-1}\binom{n-i}{r-s}}{\binom{n}{r}}$$. The total probability must sum to $$1$$ and this proves the identity (the limits are precisely the support of $$i$$).

This is known as the negative hypergeometric distribution by some authors.