Problem
COM-B2-M03-P006 Even and Odd Are Equal
#6
★★★☆☆ Level 3 of 5
Prove that for an \(n\)-element set with \(n\ge1\), the number of even-sized subsets equals the number of odd-sized subsets.
Fix one element and toggle whether it is present.
Fix an element \(a\). To each subset \(S\), assign \(S\triangle\{a\}\): if \(a\in S\), remove it; otherwise add it. The size changes by \(1\), so parity changes. The operation is its own inverse, hence a bijection between even-sized and odd-sized subsets.
An excellent example of an involution.