1
$\begingroup$

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?

  • 2
    See http://math.stackexchange.com/questions/73015.2012-04-20

1 Answers 1

4

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.

Remark: Counting the same thing in two different ways can be a powerful tool to prove identities.