Select Page

## Combinatorial Identity #1

Let us prove that

$\left( \begin{matrix} m+n \\ n \end{matrix} \right) = \sum\limits_{k=0}^{\infty }{\left( \begin{matrix} m \\ k \end{matrix} \right)\left( \begin{matrix} n \\ k \end{matrix} \right)}$

First of all, assume that m < n, so then what we need to prove is

$\sum\limits_{k=0}^{m}{\left( \begin{matrix} m \\ k \end{matrix} \right)\left( \begin{matrix} n \\ k \end{matrix} \right)} = \left( \begin{matrix} m+n \\ n \end{matrix} \right)$

Indeed, assume that we need to choose n people from m Americans and n Canadians. Then, since m < n, then we can choose k Americans for $$k\in \left\{ 0,1,2,…,m \right\}$$. The number of ways k Americans can be chosen is $$\left( \begin{matrix} m \\ k \end{matrix} \right)$$, and in order to complete the n people, I need to chose n – k Canadians, which can be done in $$\left( \begin{matrix} n \\ n-k \end{matrix} \right)$$ ways.

Hence, using the product rule, choosing n people by choosing k Americans and n – k Canadians can be done in $$\left( \begin{matrix} m \\ k \end{matrix} \right) \left( \begin{matrix} n \\ n-k \end{matrix} \right)$$ ways. But $$\left( \begin{matrix} n \\ n-k \end{matrix} \right) = \left( \begin{matrix} n \\ k \end{matrix} \right)$$, so then choosing n people by

choosing k Americans and n – k Canadians can be done in

$\left( \begin{matrix} m \\ k \\ \end{matrix} \right)\left( \begin{matrix} n \\ n-k \end{matrix} \right)=\left( \begin{matrix} m \\ k \end{matrix} \right)\left( \begin{matrix} n \\ k \end{matrix} \right)$

ways. Therefore, in total, all the ways of choosing n people are:

$\left( \begin{matrix} m+n \\ n \end{matrix} \right)=\left( \begin{matrix} m \\ 0 \end{matrix} \right)\left( \begin{matrix} n \\ 0 \end{matrix} \right)+\left( \begin{matrix} m \\ 1 \end{matrix} \right)\left( \begin{matrix} n \\ 1 \end{matrix} \right)+…+\left( \begin{matrix} m \\ m \end{matrix} \right)\left( \begin{matrix} n \\ m \end{matrix} \right)=\sum\limits_{k=0}^{m}{\left( \begin{matrix} m \\ k \end{matrix} \right)\left( \begin{matrix} n \\ k \end{matrix} \right)}$

The case for $$m\ge n$$ is proven analogously. ## Combinatorial Identity #2

Now we will prove that

$\sum\limits_{k=0}^{\infty }{\left( \begin{matrix} n \\ k \\ \end{matrix} \right)\left( \begin{matrix} k \\ m \end{matrix} \right)}=\left( \begin{matrix} n \\ m \end{matrix} \right){{2}^{n-m}}$

Assume there are n people in a given city, and assume that m people are selected randomly as winners. Now, let us consider a group of k people, then the number of ways m people can be selected from those k people is

$\left( \begin{matrix} n \\ k \end{matrix} \right)\left( \begin{matrix} k \\ m \end{matrix} \right)$

Therefore, by sweeping all possible values of k we find that the number of total ways this can be done is $$\sum\limits_{k=0}^{\infty }{\left( \begin{matrix} n \\ k \end{matrix} \right)\left( \begin{matrix} k \\ m \end{matrix} \right)}$$.

Now, this calculation could have been done differently: Choosing m people from a group of n can be done in

$\left( \begin{matrix} n \\ m \end{matrix} \right)$

ways. Now, out of the remaining n – m people who were not selected as winner, they may or may not appear for the lottery, which accounts for $${{2}^{n-m}}$$ ways, and using the product rule we conclude that the number of ways is

$\left( \begin{matrix} n \\ m \end{matrix} \right){{2}^{n-m}}$

which equating to the other calculation form leads to:

$\sum\limits_{k=0}^{\infty }{\left( \begin{matrix} n \\ k \end{matrix} \right)\left( \begin{matrix} k \\ m \end{matrix} \right)}=\left( \begin{matrix} n \\ m \end{matrix} \right){{2}^{n-m}}$

which concludes the calculation