Problem
COM-B2-M03-P017 An Involution for an Alternating Sum
#17
★★★★☆ Level 4 of 5
Give a bijective proof that \(\sum_{k=0}^{n}(-1)^k\binom nk=0\) for \(n\ge1\).
Cancel even and odd subsets by an involution.
The sum counts even-sized subsets with sign \(+\) and odd-sized subsets with sign \(-\). Fix element \(1\). The map \(S\mapsto S\triangle\{1\}\) changes the parity of the size and is its own inverse. Thus every even subset is paired with an odd subset, and each pair cancels. The sum is \(0\).
This is a basic sign-reversing involution.