Prove a combinatorial identity involving summing product of binomial coefficients

Question

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.

Answer 1

$$\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.

Answer 2

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.