An Alternating Convolution Identity via Sign-Reversing Involutions

This month’s post is on the combinatorial proof technique of sign-reversing involutions.  It’s a really clever idea that can often be applied to identities that feature alternating sums.  We’ll illustrate the technique on the following identity.

\displaystyle \sum_{k=0}^m \binom{n}{k} \binom{n}{m-k} (-1)^k = (-1)^{m/2} \binom{n}{m/2} [ m \text{ is even}].

(Here, we use the Iverson bracket notation [A], where [A] is 1 if A is true and 0 if A is false.)

This identity is interesting because there’s a lot going on here.  For one, it’s an alternating version of the famous Vandermonde identity.  But what’s happening with the right side?  Why is it zero when m is odd, and why does the parity of m/2 matter?  The sign-reversing involution technique will help us make sense of all of that.

First, \binom{n}{k} \binom{n}{m-k} can be thought of in terms of counting ordered pairs (A,B), each of which is a subset of \{1, 2, \ldots, n\}.  However, the choice of (A,B) is subject to the restriction that |A| = k and |B| = m-k.  The alternating sum on the left side of the identity is taken over all such pairs such that |A| + |B| = m, where the parity of a particular (A,B) is the parity of |A|.

We now have a combinatorial interpretation of the left side.  Now, let’s define the sign-reversing involution.  Given (A,B), let x denote the largest element in the symmetric difference A \oplus B of A and B; i.e., A \oplus B = (A-B) \cup (B-A).  Let

\displaystyle \phi(A,B) = \begin{cases} (A-\{x\}, B \cup \{x\}), & x \in A; \\ (A \cup \{x\}, B - \{x\}, & x \in B.\end{cases}

Note that \phi takes an ordered pair (A,B) such that A, B \subseteq \{1, 2, \ldots, n\} and |A| + |B| = m and maps it to another such ordered pair.  Moving the largest element x in the symmetric difference of A and B to the other set changes the number of elements in A by one and thus the parity of |A|.  This means \phi is sign-reversing.  In addition, \phi(A,B) has the same largest element x in its symmetric difference that (A,B) does; thus applying \phi to \phi(A,B) just sends x back to its original set.  Thus \phi(\phi(A,B)) = (A,B), which makes \phi an involution.

These two properties mean that \phi associates an ordered pair (A,B) of the kind we’re examining with another ordered pair that has a different parity.  Each of these pairs cancels out its associated pair in terms of evaluating the alternating sum on the left side of the identity we’re trying to prove.  Since every pair (A,B) has an associated pair that cancels it out, we have that the right side of our identity is the number of pairs (A,B) for which \phi is not defined.  Let’s count those leftover pairs now.

The only way for \phi to be undefined is for the largest element x in A \oplus B to not exist.  But that can only happen if A-B = \emptyset = B-A; in other words, A = B.  In this case, though, since |A| + |B| = m, we have |A| = |B| = m/2.  Thus when m is odd, there are no pairs (A,B) on which \phi is undefined; hence the right side of the identity is 0 when m is odd.  When m is even, there are \binom{n}{m/2} ways to choose the elements of A, and since B = A, this choice also determines B.  Since for all of these pairs A has m/2 elements, the parity of these leftover elements is the parity of m/2.

In general, this is how a sign-reversing involution argument works: Find a combinatorial interpretation of the terms in the left side of the alternating sum, then find a sign-reversing involution that maps entities with odd parity to entities with even parity and vice versa.  Counting the entities that are left over – i.e., those not paired up by the involution – will yield the right side of the identity.

For more sign-reversing involution arguments, see this post and this post.  Chapter 6 of Benjamin and Quinn’s Proofs that Really Count [1] and Chapter 5 of Aigner’s A Course in Enumeration [2] have examples as well.

(For what it’s worth, the identity can be proved more easily using generating functions, but I don’t think that approach gives as much insight into why the identity is true.)

References

  1.  Arthur T. Benjamin and Jennifer J. Quinn.  Proofs that Really Count.  MAA, 2003.
  2. Martin Aigner.  A Course in Enumeration.  Springer, 2010.

 

Advertisements
This entry was posted in binomial coefficients, combinatorics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s