Exercise 887Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Sets of even size

#even subsets#binomial#counting

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

Bijection: toggle element $1$ in/out.

Show solutionHide solution

Bijection. Map subset $S$ to $S\triangle\{1\}$ (symmetric difference with $\{1\}$ ). This changes the parity of $|S|$ and is an involution.

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