Question

If set S has n elements how many subsets have an even # of elements?

Answer 1

Question 1.

If set $S$ has $n$ elements, how many subsets have an even number of elements?

Solution.

For any $0\leq k\leq n$ the number of $k$-element subsets of an $n$-element set is $\binom{n}{k}$. Hence, the number of the sets having an even number of elements is

$\binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{2m},$

where $2m$ is the maximal even number which does not exceed $n$.

We know that the number of all the subsets is

$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=(1+1)^{n}=2^{n}.$

Since

$\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\cdots+(-1)^{n}\binom{n}{n}=(1-1)^{n}=0,$

then

$\binom{n}{0}+\binom{n}{2}+\cdots=\binom{n}{1}+\binom{n}{3}+\ldots,$

so the number of the subsets consisting of an even number of elements coincides with the number of the subsets consisting of an odd number of elements. Thus, both of these numbers equal $\frac{1}{2}\cdot 2^{n}=2^{n-1}$, $n>0$. If $n=0$, i. e. $S$ is empty, then there is only one subset of $S$ and it has even number (zero) of elements.

Answer:

\[ \begin{cases}1,&\text{if }n=0,\\

2^{n-1},&\text{if }n>0.\end{cases} \]