Exercise 483Combinatorics › Inclusion-exclusionHigh schoolAdded 3 Nov 2026

Even vs odd subsets

#even subsets#odd subsets#IE

Statement

Show that the number of subsets of an $n$ -element set with even size equals the number with odd size, for $n\ge1$ .

Hint

Toggle one element (bijection), or use $(1-1)^n=0$ .

Show solutionHide solution

Bijection. Map $S\mapsto S\triangle\{1\}$ . This is an involution changing parity.

Conclusion. Even and odd subsets are equinumerous, each count $2^{n-1}$ .