# Number of subsets with even number of elements [duplicate]

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?

• Jul 3, 2015 at 12:54

Here's a quick combinatorial method.

If $n=0$ then clearly there is $1$ such subset, namely the empty set itself.

If $n>0$, list the elements of $X$ as $$x_1, x_2, \dots, x_n$$ A subset $S \subseteq X$ with an even number of elements is determined by its intersection with $\{ x_1, \dots, x_{n-1} \}$: if the intersection has an even number of elements then $x_n \not \in S$, and if it has an odd number of elements then $x_n \in S$.

Thus the number of subsets of $X$ with an even number elements is equal to the number of subsets of $\{ x_1, \dots, x_{n-1} \}$, namely $2^{n-1}$.

Alternatively, convince yourself that the number of subsets with an even number of elements is $$\frac{1}{2} \left( \sum_{k=0}^n \binom{n}{k} + \sum_{k=0}^n (-1)^k \binom{n}{k} \right)$$ and apply the binomial theorem.

In total there are $$2^n$$ subsets of $$X$$.

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

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

So in both cases the answer is $$2^{n-1}$$.

Hint

There is $\displaystyle\binom{n}{2k}$ different sets of size $2k$ for $1 \leq k \leq n/2$.

Formulate then your result as a sum and simplify it.