Example of Combinatorial Identities

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