Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
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 \}$. –  Chris Eagle Dec 19 '11 at 10:51
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.