# Proving a binomial coefficient identity [duplicate]

I'm having some trouble with the following proof: $$\sum^k_{a=0} {{n}\choose{a}}{{m}\choose{k-a}} = {{n+m}\choose{k}}$$

I'm trying to prove this to learn a couple of things about the Pascal's triangle. I don't know where to start on the proof. I have tried expanding both sides using the binomial coefficient property but have had no luck.

## marked as duplicate by David K, Daniel W. Farlow, hardmath, Ben Sheller, Kamil JaroszApr 11 '16 at 14:23

• This is Vandermonde's Identity and has been asked about several times on this site already. Here is one such link. There is likely a better link to use to mark as duplicate however. – JMoravitz Apr 10 '16 at 21:29
• @JMoravitz I didn't know the name of the identity, otherwise I would have just googled it. Thanks – TheSalamander Apr 10 '16 at 21:32

This is called Vandermonde's identity. To prove it, write $(1+x)^{n+m}=(1+x)^n(1+x)^m$ and look at the coefficient of $x^k$ on both sides.
Suppose you need to choose $k$ elements out of a possible $n+m$. Divide the total list into the first $n$ and the remaining $m$. Your choice must consist of $a$ from the first part (where $a\in \{0,\cdots k\}$) and $k-a$ from the second part. Conversely, any two such collections combine to give you a viable collection of $k$.
The RHS counts the number of ways of selecting a committee of $k$ people from $n$ women and $m$ men.
The expression $$\binom{n}{a}\binom{m}{k - a}$$ counts the number of ways of selecting a committee of $k$ people consisting of $a$ women and $k - a$ men selected from selected from a group consisting of $n$ women and $m$ men. Thus, the summation on the LHS counts all the ways of selecting a committee of $k$ people can be selected from $n$ women and $m$ men.