# Identity of binomial coefficients with a series

I never really used any series/infinite sums and now I should proove the following identity: $$\sum\limits_{k=0}^{\infty}\binom{m}{k}\binom{n}{l-k}=\binom{m+n}{l}$$ Can you please explain me, how to handle the infinite sum and furthermore give some hints on how to solve this problem?

• The finite sum is in fact finite, since $\binom mk=0$ whenever $k<0$ or $k>m$. One way to prove this would be a combinatorial argument - try to think about number of subsets of $\{1,2,\dots,m+n\}$ which is determined by $\binom{m+n}l$. Can you relate them to subsets of $\{1,\dots,m\}$ and $\{m+1,\dots,m+n\}$ somehow?\\ I should also mention that this is a well-known identity, it is called Chu-Vandermonde Identity. I believe we have proofs of this identity in some answers on this site. – Martin Sleziak Apr 20 '12 at 10:01
• – joriki Apr 20 '12 at 11:18

There are $m$ boys and $n$ girls in a class. The right-hand side counts the number of ways to choose $l$ people from these $m+n$ people.
The left-hand side is a finite sum, for $\binom{x}{y}$ is defined to be $0$ if $y>x$. So the left-hand side is equal to $$\sum_{k=0}^{m}\binom{m}{k}\binom{n}{l-k}.$$ For any fixed $k$, the number $\binom{m}{k}\binom{n}{l-k}$ counts the number of ways of choosing $k$ boys and $l-k$ girls, for a total of $l$ people, of whom $k$ are boys and the rest girls.
So $\binom{m}{0}\binom{n}{l-0}$ counts the number of ways to choose $0$ boys and $l$ girls. Also, $\binom{m}{1}\binom{n}{l-1}$ counts the number of ways to choose $1$ boy and $l-1$ girls. And $\binom{m}{2}\binom{n}{l-2}$ counts the number of ways to choose $2$ boys and $l-2$ girls. Continue. As we sum over all $k$, we get a count of all the ways to choose $l$ people from the group, since we have accounted for all possible numbers of boys. This is equal to the right-hand side. the right-hand side.