Having trouble understanding summation identity

Question

I'm having trouble understanding how the right side of this summation is equal to the left side. Any information would be helpful!

$$\sum_{k=0}^{n} {r \choose k}{s \choose n-k}={r+s \choose n}$$

Answer 1

Firstly, there's an error in your formula - it should be $r+s\choose n$ on the right. Second, here's how it works:

Conceptually, suppose you have $r$ objects in one bucket and $s$ objects in another, and you want to draw $n$ objects in total between them. How many ways can you do that?

Well, clearly you could just pour everything into one bucket and take $n$ objects out, so there are $r+s\choose n$ ways of doing it (i.e. the right-hand side).

Or, you could draw nothing from the first bucket and $n$ from the second. There are ${r \choose 0}{s \choose n}$ ways to do that.

Or you could draw $1$ thing from the first bucket and $n-1$ from the second. There are ${r \choose 1}{s \choose n-1}$ ways for that.

Or you could draw $k$ things from the first bucket and $n-k$ from the second, for some $k \in \{2, \ldots, n\}$. There are ${r \choose k}{s \choose n-k}$ ways to do that.

Clearly, once you've dealt with all the possible combinations of drawing some number from the first bucket and the remainder from the second, you've covered all possible combinations in general, so the total number of ways to select the $n$ objects is the sum of all of the above, thus there are $\sum_{k=0}^n {r \choose k}{s \choose n-k}$ ways to choose the objects, which is the left-hand side.

But the two ways of doing that are equivalent, hence the equality you've been given.

Answer 2

This is known as Vandermonde's Identity. It says that for each way to choose $n$ items from a set of $r+s$ items, for some $k$ we must choose $k$ from the set of $r$ and $n-k$ from the set of $s$. This translates to $$ \binom{r+s}{n}=\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}\tag{1} $$

---

Another way to look at this is to look at $$ (1+x)^{r+s}=(1+x)^r(1+x)^s\tag{2} $$ Then, using the Binomial Theorem, we get $$ \begin{align} \sum_{n=0}^{r+s}\binom{r+s}{n}x^n &=\sum_{i=0}^r\binom{r}{i}x^i\sum_{j=0}^s\binom{s}{j}x^j\\ &=\sum_{n=0}^{r+s}\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}x^kx^{n-k}\\ &=\sum_{n=0}^{r+s}\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}x^n\tag{3} \end{align} $$ Comparing coefficients of $x^n$ in $(3)$, we get $(1)$.