$\sum_{x+y =c}{a\choose x}{b\choose y} = {a+b\choose c}$

Question

When trying to prove a problem I find that I need the above formula to be true, but I have no idea how to prove it. I am trying to prove that a given probability mass function is equivalent to a hypergeometric distribution and this identity pops up.

Answer 1

The combinatoric proof is that you have $a+b$ things and are counting the ways to choose $c$ of them. That is directly the interpretation of the right hand side. The left assumes you break the $a+b$ into a group of $a$ and a group of $b$, then choose $x$ of the $a$ and $c-x$ of the $b$. When you sum over $x$ from $0$ to $c$ you get all the possibilities.