This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!
First identity. This is Vandermonde’s Identity.
\[
\sum_{k=0}^p {m \choose k}{n \choose p-k} = {m+n \choose p}
\]
[Show Solution]
Suppose we have a population of $m$ boys and $n$ girls and we’d like to count how many groups of $p$ people we can make. This is clearly $m+n \choose p$. Another way to count is to let $k$ be the number of boys in our group. We can choose the boys in $m \choose k$ ways, and the remaining $p-k$ group members, which must be girls, can be chosen in $n \choose p-k$ ways. So there are ${m \choose k}{n \choose p-k}$ groups that contain $k$ boys. Summing this over all possible $k$ gives us the total number of groups with any number of boys.
Second identity. This is the Christmas Stocking Identity. It is also sometimes called the Hockey-Stick Identity.
\[
\sum_{k=0}^m {n+k \choose n} = {m+n+1 \choose n+1}
\]
[Show Solution]
Suppose we have a set of $m+n+1$ marbles and we would like to choose a subset of size $n+1$. There are $m+n+1 \choose n+1$ ways of doing this. Counting differently, suppose the marbles are numbered $1,2,\dots,m+n+1$. Since we are choosing $n+1$ marbles, the largest-numbered marble in our subset must have label $n+1$ or larger. If the largest-numbered marble in our subset has label $n+k+1$ ($k=0,1,\dots,m$), then the remaining $n$ marbles must be selected among the $n+k$ smaller-numbered marbles, which can be done in $n+k \choose n$ ways.
Third identity. This one looks similar to the first one, but notice that the upper coefficient is varying this time.
\[
\sum_{k=0}^p {k \choose m}{p-k \choose n} = {p+1 \choose m+n+1}
\]
[Show Solution]
Suppose we have a set of $p+1$ marbles and we’d like to choose a subset of size $m+n+1$. There are $p+1 \choose m+n+1$ ways of doing this. Counting differently, suppose the marbles are numbered $1,2,\dots,p+1$. We’ll select our subset in order of ascending labels: first we’ll choose the $m$ smallest-numbered marbles, then the middle marble, and then the $n$ remaining larger-numbered marbles. If our middle marble happens to be labeled $k+1$, there are $k$ smaller marbles (labeled $1,2,\dots,k$) among which we need to choose $m$, so $k \choose m$ ways. Likewise, there are $p-k$ larger marbles (labeled $k+2,k+3,\dots,p$) among which we need to choose $n$, so $p-k \choose n$ ways. As we sum over all possible values of the middle marble, we obtain the expression on the left-hand side.
One nit: For the 3rd identity, it looks like there is a boundary problem on the summation.
As is, I don’t think the 3rd identity is well defined unless m=0, because C(k,m) = k!/m!(m-k)!. That denominator at some point necessarily has a negative factorial (which does not exist even as gamma function) unless m = 0. Perhaps you meant for the lower bound of the summation to be k =m, instead of k=0?
Otherwise, some really good binomials calcs here.
The convention is that $n \choose k$ = 0 if $k \gt n$. This makes intuitive sense; there are zero ways to choose 3 things from a set of 2 things. There is a more rigorous explanation here along with a generalization to the case where $n$ and $k$ are complex numbers.
We could avoid this convention as you mention by changing the lower bound to $k=m$. But we would also have to change the upper bound to $k=n-p$ (so there are no problems with the second term).