Let $M$ be a non-empty set. Show that $M$ has as many subsets with an odd number of elements as subsets with an even number of elements.
I already found a solution which said to use the identity $\sum_{k = 0}^{n} (-1)^{k} {n \choose k} = 0$, which clearly can be seen that the sign alternates for odd and even $k$. I also found a prove of the identity here. The point is that, I want to know whether this can be proved in any other method apart from that identity, and if yes, how?
Best Answer
Since the set is non-empty we can choose $m\in M$. Then there is a perfect pairing between the set of subsets containing $m$ and the set of subsets which don't contain $m$ (just add $m$ if it isn't there, and delete it if it is). But in each such pair one subset has an even number of elements and the other has an odd number of elements.
As an explicit example, suppose your original set has three elements $\{A,B,C\}$. Say we choose the element $A$. Then The pairing is $$\left[\emptyset, \{A\}\right], \left[\{B\}, \{A,B\}\right],\left[\{C\}, \{A,C\}\right],\left[\{B,C\}, \{A,B,C\}\right]$$