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.