Exercise 406Combinatorics › Binomial coefficientsHigh schoolAdded 3 Nov 2026

Even vs odd subsets

#even subsets#odd subsets#alternation

Statement

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

Hint

Bijection: toggle element $1$ .

Show solutionHide solution

Solution

Bijection. Map subset $S$ to $S\triangle\{1\}$ (add or remove element $1$ ). This changes the parity of $|S|$ and is its own inverse, so it is a bijection.

Conclusion. Each count is $2^{n-1}$ .

Even vs odd subsets

Statement

Solution

More problems in Binomial coefficients