6
$\begingroup$

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?

  • 3
    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 \}$.2011-12-19

2 Answers 2

7

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.

  • 0
    In fact, I was confused about that part. The reason I wrote it as $k$ because I want to use the induction hypothesis.2011-12-19
8

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.

  • 0
    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.2011-12-20