Double-counting, Part 2

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]

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]

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]

3 thoughts on “Double-counting, Part 2”

  1. 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.

    1. The convention is that $n \choose k$ = 0 if $k \ge 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).

Leave a Reply

Your email address will not be published. Required fields are marked *