This from an exercise in Aigner's book where one has to evaluate $\sum_{k\ge 0} (-1)^k \binom{n}{k}^2$ using sign reversing involutions. When $n$ is odd, the problem is trivial : let $[n] = \{1,2,\dots,n\}$ consider all pairs of subsets $\{ (A,B) \in 2^{[n]} \times 2^{[n]} : |A| = |B| \}$, and $(A,B)$ has sign $(-1)^{|A|}$ and the sign-reversing involution is $(A,B) \to ([n]-A,[n]-B)$. Any hints on how to approach this problem for even $n$ will be appreciated.
sign reversing involution proof of a combinatorial identity
10
$\begingroup$
combinatorics
1 Answers
10
Consider the set of pairs $(A,B)$ of subsets of $\{1,\ldots,n\}$ such that $|A|+|B|=n$ with weight $(-1)^{|A|}$. The exceptional pairs where the involution is not defined are those where $A=B$. For each other pair $(A,B)$ take the smallest element of the symmetric difference of $A$ and $B$ and move it from one set to the other. The symmetric difference of the two new sets is the same, so this is an involution, and it is weight-reversing.
-
0That's very neat! – 2010-10-14