2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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/… ). $\endgroup$ Aug 18, 2019 at 18:41
  • 3
    $\begingroup$ As for the second identity, note that $i\dbinom{i-1}{s-1} = s\dbinom{i}{s}$. $\endgroup$ Aug 18, 2019 at 18:43
  • 1
    $\begingroup$ Thank you for your comments! They actually solved all my problem. $\endgroup$
    – Tom
    Aug 18, 2019 at 18:53

2 Answers 2

0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .