5
$\begingroup$

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}$$

$\endgroup$
5
  • 4
    $\begingroup$ en.wikipedia.org/wiki/Vandermonde%27s_identity $\endgroup$ Dec 15, 2016 at 23:22
  • $\begingroup$ RHS is {r+s \choose n}. Apart from that where do you have difficulty ? $\endgroup$
    – G Cab
    Dec 15, 2016 at 23:23
  • $\begingroup$ I think the RHS should have an $n$ on the bottom, not a $k$ $\endgroup$
    – GuPe
    Dec 15, 2016 at 23:23
  • 1
    $\begingroup$ I say look at the wiki page linked above, its got like 3 different proofs. $\endgroup$ Dec 15, 2016 at 23:26
  • $\begingroup$ oops yes its a n not a k on the bottom, thanks I will look through the wiki's! $\endgroup$
    – J. Shean
    Dec 15, 2016 at 23:28

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you so much, this was a perfect explanation to help understand the problem! $\endgroup$
    – J. Shean
    Dec 15, 2016 at 23:33
  • $\begingroup$ @J. Shean Then why not upvote to say thanks? $\endgroup$
    – The Count
    Dec 15, 2016 at 23:38
  • $\begingroup$ Combinatorial proofs are the bestest. $\endgroup$ Dec 16, 2016 at 11:39
10
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .