Question

Let S be a finite nonempty set. Show that the number of subsets of S of even cardinality equals the number of subsets of S of odd cardinality.

Answer 1

Let $|S|=n.$ In total there are $2^n$ subsets of $S$.

If $n$ is odd then there is a one-to-one correspondence between sets with even cardinality and sets with odd cardinality. Subset $A$ corresponds with its complement $S\setminus A$. Consequently, the number of subsets with even cardinality equals the number of subsets with odd cardinality. So this number is $\frac{1}{2}2^n=2^{n-1}.$

If $n$ is even then put one element $a\in S$ aside. With the trick described above we find that $S\setminus\{a\}$  has $2^{n-2}$ subsets with even cardinality and also $2^{n-2}$ subsets with odd cardinality. The subsets of $S\setminus\{a\}$  with odd cardinality become subsets $S$  with even cardinality if element $a$ is added to each of them. This gives us $2^{n-2}+2^{n-2}=2^{n-1}$ subsets of $S$ with even cardinality. So in both cases the number of subsets of $S$ of even cardinality equals the number of subsets of $S$ of odd cardinality.