sign reversing involution proof of a combinatorial identity
Solution 1:
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.