Simplifying $\big(\sum_{i=0}^n\binom{k}{i}\binom{M-k}{n-i}\frac{k-i}{M-n}\big)/{\binom{M}{n}}$

Question

Show that $$\frac{\sum_{i=0}^n\binom{k}{i}\binom{M-k}{n-i}\frac{k-i}{M-n}}{\binom{M}{n}}=\frac{k}{M},$$ where $M-k>n$ and $k>n$

From Vandermonde's identity, I get $\sum_{i=0}^n\binom{k}{i}\binom{M-k}{n-i}=\binom{M}{n}$.

But what about the sum of the product in the numerator? Any hint will be helpful.

Answer 1

Note that

$$\begin{align*} \sum_{i=0}^n\binom{k}i\binom{M-k}{n-i}(k-i)&=\sum_{i=0}^nk\binom{k-1}i\binom{M-k}{n-i}\\ &=k\sum_{i=0}^n\binom{k-1}i\binom{M-k}{n-i}\\ &=k\binom{M-1}n\;, \end{align*}$$

so your numerator is

$$\frac{k}{M-n}\binom{M-1}n=\frac{k(M-1)!}{n!(M-n)!}=\frac{k}M\binom{M}n\;.$$

Answer 2

If you want to take a probabilistic approach, observe that the sum is $$ \mathbb{E}\Big[\frac{k-X}{M-n}\Big]=\frac{k}{M-n}-\frac{1}{M-n}\mathbb{E}[X] $$ where $X$ is a hypergeometric random variable, i.e. $X$ counts the number of black balls in a sample of $n$ balls taken from an urn without replacement if there are $k$ black balls and $M-k$ white balls total.

Answer 3

You can also produce this equality using a combinatorial argument, following Brian's first simplification. Note that your identity is equivalent to showing that for $n \leq k \leq M$, $$ \sum_{i=0}^n {k \choose i} {M-k \choose n-i} (k-i) = k {M \choose n}\frac{M-n}{M} = k {M-1 \choose n}. $$

Now suppose that you have $M$ people of whom $k$ are girls and $M-k$ are boys. You wish to have a team of $n+1$ people including a leader who is a girl. The RHS above is the number of ways to pick the leader first and then pick the $n$ non-leader members of the team out of the remaining $M-1$ potential team members. For the LHS, you sum over the number $i$ of non-leader girl team members. For each $i$, you

• choose the $i$ non-leader girl team members out of the $k$ girls,
• choose the $n-i$ boy team members out of the $M-k$ boys,
• choose the leader out of the remaining $k-i$ girls.