Even and odd subsets
Task number: 3324
Show that for every non-empty finite set the number of subsets of even size (i.e. with an even number of elements) equals the number of subsets of odd size.
Solution
We proceed by induction on the size of the underlying set. A single-element set has two subsets: the empty set (of even size) plus the set itself (of odd size).
Induction step \(n \to n+1\): we choose any element \(a\). By the inductive hypothesis, the number of even subsets not containing \(a\) is the same as the number of odd subsets not containing \(a\).
However every even subset containing \(a\) consists of \(a\) plus an odd number of other elements, and conversely.
So the total number of even subsets = number of even subsets with \(a\) + number of even subsets without \(a\) = number of odd subsets without \(a\) + number of even subsets without \(a\) = number of odd subsets without \(a\) + number of odd subsets with \(a\) = the total number of odd subsets.
