# Is there a binomial identity for this expression $\frac{\binom{r}{k}}{\binom{n}{k}}$?

What I'm trying to prove is this summation: $$\sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k - i}}{\dbinom{n}{k}} \cdot i = \dfrac{r}{n} \cdot k$$ I used induction on $k$ as follows:

$$LHS = \sum_{i=0}^{k + 1} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k + 1 - i}}{\dbinom{n}{k + 1}} \cdot i$$ $$= \sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \cdot \dbinom{n - r}{k - i}}{\dbinom{n}{k}} \cdot i + \dfrac{\dbinom{r}{k + 1} \cdot \dbinom{n - r}{k + 1 - (k + 1)}}{\dbinom{n}{k+1}} \cdot (k + 1)$$ $$= \dfrac{rk}{n} + \dfrac{\dbinom{r}{k + 1} \cdot \dbinom{n - r}{0}}{\dbinom{n}{k+1}} \cdot (k + 1)$$ $$= \dfrac{rk}{n} + \dfrac{\dbinom{r}{k + 1}}{\dbinom{n}{k+1}} \cdot (k + 1)$$

Then I was stuck with the expression $\dfrac{\dbinom{r}{k + 1}}{\dbinom{n}{k + 1}}$, where $k + 1 \leq r \leq n$. I guess I need a clever trick here to simplify the left hand side, any idea?

-
This looks quite close to the Chu-Vandermonde identity (en.wikipedia.org/wiki/Chu-Vandermonde_identity), especially when written as in equations (7a,7b) here (en.wikipedia.org/wiki/Binomial_coefficient#equation_7a). I would recommend rewriting it as: $$\sum_{i=0}^{k}\frac{i}{r}\binom{r}{i}\binom{n-r}{k-i} =\frac{k}{n}\binom{n}{k} =\binom{n-1}{k-1}$$ (handling $n=0$ & $k=0$ separately) and going from there. – bgins Dec 19 '11 at 10:49
Hint: The left-hand side is the expected number of elements of $X$ which are in $\{1, 2, \ldots, r \}$, where $X$ is a randomly chosen size $k$ subset of $\{1, 2, \ldots, n \}$. – Chris Eagle Dec 19 '11 at 10:51

We don't need induction: \begin{align*} \sum_{i=0}^k\binom ri\binom{n-r}{k-i}i&=\sum_{i=1}^k\frac{r!}{(i-1)!(r-1-(i-1))}\binom{n-r}{k-i}\\ &=r\sum_{l=0}^{k-1}\binom{r-1}{l}\binom{n-r}{k-1-l}\\ &=r\binom{n-r+r-1}{k-1}\\ &=r\binom{n-1}{k-1}\\ &=\frac rn\frac{n!}{(k-1)!(n-k)!}\\ &=\frac {rk}n\binom nk, \end{align*} the third equality is Chu-Vandermonde identity.

-
Many thanks for an elegant proof. However, I still wonder if my approach can work without using Chu-Vandermonde identity. – Chan Dec 19 '11 at 12:01
I don't understand your step from the first line to the second. – Davide Giraudo Dec 19 '11 at 12:05
I just separated the sum, $\sum_{i=0}^{k}$ + $(k+1)th$ term. – Chan Dec 19 '11 at 12:13
But why did $k+1$ become $k$ in the sum? – Davide Giraudo Dec 19 '11 at 12:36
In fact, I was confused about that part. The reason I wrote it as $k$ because I want to use the induction hypothesis. – Chan Dec 19 '11 at 13:08

As Chris Eagle points out, your binomial sum is calculating an expected value. From that point of view, there are at least two ways to proceed. Suppose you have an urn with $n$ balls, $r$ of which are red and the rest of which are blue. You choose $k$ balls at random from the urn, without replacement. Let $Y$ be the number of red balls chosen. Then $$P(Y = i ) = \dfrac{\dbinom{r}{i} \dbinom{n - r}{k - i}}{\dbinom{n}{k}};$$ i.e., the number of ways to choose $i$ red balls from the $r$ total red balls times the number of ways to choose $k-i$ blue balls from the $n-r$ total blue balls divided by the number of ways to choose $k$ balls from $n$. (The variable $Y$ has what's called a hypergeometric distribution.) Your binomial sum is calculating $E[Y]$.

First way. Use indicator variables.

Let $X_i = 1$ if the $i$th ball chosen is red. Then $$E[Y] = \sum_{i=1}^k E[X_i] = \sum_{i=1}^k P(X_i \text{ is red}) = \sum_{i=1}^k \frac{r}{n} = \frac{kr}{n}.$$

Second way. This one is similar to Davide Giraudo's answer.

\begin{align} \sum_{i=0}^{k} \dfrac{\dbinom{r}{i} \dbinom{n - r}{k - i}}{\dbinom{n}{k}} i &= \sum_{i=1}^{k} \frac{r! k! (n-k)!}{(i-1)! (r-i)! n!} \binom{n-r}{k-i} \\ &= \frac{kr}{n} \sum_{i=1}^{k} \frac{(r-1)! (k-1)! (n-k)!}{(i-1)! (r-i)! (n-1)!} \binom{n-r}{k-i} \\ &= \frac{kr}{n} \sum_{i=1}^{k} \frac{\dbinom{r-1}{i-1} \dbinom{n-r}{k-i}}{\dbinom{n-1}{k-1}} \\ &= \frac{kr}{n} \sum_{i=0}^{k-1} \frac{\dbinom{r-1}{i} \dbinom{(n-1)-(r-1)}{k-1-i}}{\dbinom{n-1}{k-1}} \\ &= \frac{kr}{n}, \end{align} where the last equality follows because the summand is the probability of choosing $k-1$ balls from an urn containing $n-1$ balls, $r-1$ of which are red, and obtaining $i$ red balls. Summing up those probabilities over all possible values of $i$ must give $1$. (This argument for the last equality is really equivalent to the Chu-Vandermonde identity cited by Davide.)

Also, there's a mistake in the second line of your argument. The summation should have $\dfrac{\dbinom{r}{i} \dbinom{n - r}{k+1 - i}}{\dbinom{n}{k+1}}i,$ not $\dfrac{\dbinom{r}{i} \dbinom{n - r}{k - i}}{\dbinom{n}{k}}i.$ Because of that I think induction will be difficult here.

-
Chris's hint was my original problem since I wanted to generalize a problem with $n$ items, $k$ chosen, and $r$ defective items, where the question is asking for the expected number of defective items. That's how this identity proof came from. By the way, very well written answer. Thank you. – Chan Dec 20 '11 at 2:43