The number of odd size subsets is equal to the number of even size subsets 
Prove that the number of subsets with odd number of elements is equal to the number of subsets with even number of elements.

I'm not sure how to approach this problem.  Is this even true for me to prove.  For example, the set {null} contain only one subset, itself, which is even.  Thus, prove by contradiction?
 A: Hint: If you set has $n$ elements, your problem is to show $$ \sum_{i=0}^n (-1)^i \binom{n}{i}=0.$$ Do you know the binomial theorem? 
A: Number the members of the set $1,2,3,4,\ldots,n$.
For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:


*

*If $1$ is a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements.

*If $1$ is not a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.


For example, suppose the set is $\{1,2,3,4\}$.  Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements:
$$
\begin{array}{rcl}
\text{even} & & \text{odd} \\
\hline
\varnothing & \leftrightarrow & \{1\} \\
\{1,2\} & \leftrightarrow & \{2\} \\
\{1,3\} & \leftrightarrow & \{3\} \\
\{1,4\} & \leftrightarrow & \{4\} \\
\{2,3\} & \leftrightarrow & \{1,2,3\} \\
\{2,4\} & \leftrightarrow & \{1,2,4\} \\
\{3,4\} & \leftrightarrow & \{1,3,4\} \\
\{1,2,3,4\} & \leftrightarrow & \{2,3,4\}
\end{array}
$$
This won't work with the empty set because we don't have an element to which we can assign the number $1$.
A: It's false for the empty set (and meaningless for infinite sets).
For non-empty (finite) sets $S$, there exists an element $x \in S$.  We can "pair up" any subset $T \subseteq S$ with $T \,\triangle\, \{x\}$, where $\triangle$ denotes the symmetric difference.
In this way, we partition $S$ into pairs $\{T,T \,\triangle\, \{x\}\}$, and in each pair is an odd-sized set, and an even-sized set.
A: We can do it by induction. The result is true for $1$-element sets.
Suppose it is true for all $k$-element sets. We show it is true for all $(k+1)$-element sets.
So we have a set $B$ of $k+1$ people, including George. How many subsets of $B$ are there with an odd number of elements? Let $A$ be the set of all people except George.
To make a subset of $B$ with an even number of elements, we either (i) take a subset of $A$ with an even number of elements or (ii) take a subset of $A$ with an odd number of elements, and add George.
By the induction hypothesis, there are $2^{k-1}$ sets of type (i), and $2^{k-1}$ sets of  type (ii), for a total of $2^k$. This is half of $2^{k+1}$. 
