# Proving a combinatorial identity without double counting

Consider the following problem:

We have a collection of m white and n black balls. We pick k balls (km+n) without replacement. What is the expected number of white balls in the sample?

Counting method 1: The ratio of white balls in the collection is m/(m+n). If we repeatedly sample the collection, we expect that on average, our sample has the same ratio. Therefore, the expected number of white balls in a sample of size k is km/(m+n).

As a side note, I think the above argument somehow depends on the unbiasedness of
the mean estimator. Am I right?


Counting method 2: We directly compute the expected number of white balls in the sample:

$$\frac{\sum_{i=0}^{k} i\binom{m}{i}\binom{n}{k-i}}{\binom{m+n}{k}} \enspace.$$

So, we reach at the identity: $$\sum_{i=0}^{k} i\binom{m}{i}\binom{n}{k-i} = \frac{km}{m+n}\binom{m+n}{k} \enspace.$$

How to prove the above result without double counting?

It seems to be provable using Vandermonde's identity as well as $$i\binom{m}{i} = m\binom{m-1}{i-1}$$. But is there a simpler approach (which does not depend on extra identities such as Vandermonde's)?

• Presumably we are picking without replacement. Your expression is right. For a more formal but simple proof one can use indicator random variables. Commented Mar 19, 2016 at 22:13
• I think the approach using Vandermonde is the simplest. Commented Mar 19, 2016 at 22:52
• @AndréNicolas: Could you please elaborate? My understanding is that per each ball, one assigns an indicator r.v., which is 1 is the ball is picked in the sample, and 0 otherwise. Did I get it right? Commented Mar 20, 2016 at 13:35
• @M.S.Dousti: It is short, but I will write it out. Commented Mar 20, 2016 at 14:01

If we are looking to evaluate

$$\sum_{q=0}^k q{m\choose q}{n\choose k-q} = \sum_{q=1}^k q{m\choose q}{n\choose k-q} = m \sum_{q=1}^k {m-1\choose q-1}{n\choose k-q}$$

there is a very simple proof using the integral representation

$${n\choose k-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-q+1}} (1+z)^n \; dz.$$

This is zero when $q\gt k$ so we may extend the sum to infinity to get

$$\frac{m}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^n \sum_{q\ge 1} {m-1\choose q-1} z^q \; dz \\ = \frac{m}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^n z (1+z)^{m-1} \; dz \\ = \frac{m}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k}} (1+z)^{m+n-1} \; dz.$$

This is

$$m{m+n-1\choose k-1} = \frac{km}{m+n} {m+n\choose k}.$$

• +1. This answer taught me a lot, thanks! But I'll wait to see if a more "elementary" answer shows up. Commented Mar 20, 2016 at 13:33

For $i=1$ to $k$, define the indicator random variable $X_i$ by $X_i=1$ if the $i$-th ball picked is white, and by $X_i=0$ otherwise. Then the number $W$ of white balls picked is given by $$W=X_1+X_2+\cdots+X_k.$$ By the linearity of expectation, we have $$E(W)=E(X_1)+E(X_2)+\cdots+E(X_k).\tag{1}$$ For any $i$, the probability that the $i$-th ball picked is white is $\frac{m}{m+n}$. This is because any ball is just as likely as any other to be the obe picked $i$-th.

Thus $\Pr(X_i=1)=\frac{m}{n}$, and therefore $E(X_i)=\frac{m}{m+n}$. It follows from (1) that $E(W)=k\cdot \frac{m}{m+n}$.

• Thanks for elaboration. I assume this corresponds to (and further formalizes) counting method 1 in the question, right? Commented Mar 20, 2016 at 14:15
• You are welcome. One can think of it as a formal version of your first argument, with a proof of unbiasedness thrown in. Here the sampling is without replacement, but the very nice thing about linearity of expectation is that it does not require independence (the $X_i$ are not independent). Commented Mar 20, 2016 at 14:21
• Great. I always loved your answers; they're so inspiring! Commented Mar 20, 2016 at 14:27