Number of subsets of A∪B that contain an odd number of elements So I have a problem which defines two sets: $A = \{1,3,5\}$  and $B = \{ 1,2,3,4\}$.  The question asks for the number of subsets of $A \cup B$ that contain an odd number of elements.  I know the answer is $2^{5-1} = 2^4$ but I do not know why.  I asked a professor what if the question asked for even numbers and he said it would be the same. I know that the number of power sets is $2^n$ where $n$ represents the number of elements in the set. I even tried writing out each subset in the power set.
 A: First of all, there is no point in specifying $A$ and $B$ separately, since they don't occur separately in the condition (it would be different if for instance you were obliged to choose at least one element from $A$ and also at least one from $B$).
So you must choose an odd number of element from $C=A\cup B$ which has say $n$ elements. Supposing $n>0$, arbitrarily remove an element$~c$ from $C$ to form $C'$ of $n-1$ elements. Now any subset of $C$ can be completed to form an odd-numbered subset of $C$: if it already had an odd number of elements, just leave it as-is, and otherwise add $c$ to change the even-numbered subset to an odd-numbered subset of $C$. The number $2^{n-1}$ of subsets of $C'$ gives your answer. If instead you wanted an even numbered subset of $C$, the $2^{n-1}$ subsets of $C'$ would still count them, but the completion procedure would be opposite.
The case $n=0$ is a bit special: here there is $1$ even-numbered subset, and $0$ odd-numbered subsets.
A: The size of power set of S, $|P(S)|$ is $\sum\limits_{i=0}^{|S|} {|S| \choose i} = \sum\limits_{i=0}^{|S|} {|S|-1 \choose i-1} + {|S|-1 \choose i} =  2^{|S|}$.
And, what you want is $\sum\limits_{i=0}^{\lfloor|S|/2\rfloor} {|S| \choose 2i} = 2^{|S|-1}$ for the sum of the size of subsets where the size is even.
Observe that:
$\sum\limits_{i=0}^{\lfloor|S|/2\rfloor} {|S| \choose 2i} = {|S|-1 \choose -1} + {|S|-1 \choose 0} + {|S|-1 \choose 1} + {|S|-1 \choose 2} + .. + {|S|-1 \choose \lfloor|S|/2\rfloor-1} + {|S|-1 \choose 2\lfloor|S|/2\rfloor} = \sum\limits_{i=0}^{|S|-1} {|S|-1 \choose i} = 2^{|S|-1}$
And the argument is the same for odd sized subsets.
A: $A \cup B = \{1,2,3,4,5\}$ contains an odd number of elements.
If $S$ is a subset of $A \cup B$ containing an odd number of elements, then its complement $(A \cup B) \setminus S$ is a subset $A \cup B$ containing an even number of elements. Conversely, if $S$ contains an even number of elements, then its complement contains an odd number of elements. Furthermore, the complement function $S \mapsto (A \cup B) \setminus S$ is a bijection. Since there is a bijection between the set of subsets containing an odd number of elements and the set of subsets containing an even number of elements, there are as many subsets containing an odd number of elements and subsets containing an even number of elements.
Since the total number of subsets is the cardinal of the powerset $2^{|A \cup B|} = 2^5$, the number of subsets with an odd number of elements is half of that, $2^5/2 = 2^4$.
Note that if $A \cup B$ had an even number of elements, the complement function wouldn't take an odd-cardinal subset to an even-cardinal subset, so the argument above wouldn't hold. Nonetheless, it's still true that there are as many subsets of odd and even cardinality, as long as the set is not empty. There is a simple way to deduce this from the odd case.

 Hint: if $S$ has an even number of elements and is not empty, then $S = R \cup \{a\}$ with $a \notin R$ and $R$ has an odd number of elements.

