# How many subsets with an odd number of elements does a set with 10 elements have?

How many subsets with an odd number of elements does a set with $$10$$ elements have?

I came up with this solution:

$${10 \choose 1} + {10 \choose 3} + {10 \choose 5}+ {10 \choose 7} + {10 \choose 9} =512$$.

But the solutions says it's $$2^9=512$$, which I don't kinda get. Aren't you counting the number of subsets with, for example, $$2$$ elements? (I know it's the same solution, it just doesn't make sense to me).

Can someone explain me why this is correct and what's the reasoning behind this?

One way to see this combinatorially is to consider the $$10$$ elements in some order. With the first $$9$$ elements, you have a free choice of either including it or not including it, for $$2$$ choices each. However, there's no choice for the $$10$$ element, as it must be included if the total # so far is even, and not included if the total # is odd. Thus, as there are $$2$$ choices for each of the first $$9$$ elements, there are $$2^9$$ choices overall.

Start with a ten element set and take one element out, calling it $$x$$. We now have a nine element set. For each subset, $$S$$, of the nine element set, either

• $$S$$ contains an odd number of elements, so should be counted as a subset of the ten element set containing an odd number of elements.
• $$\{x\} \cup S$$ has an odd number of elements, so should be counted as a subset of the ten element set containing an odd number of elements.

There are $$2^9$$ subset of a nine element set. We have shown that every one of these can be made into a subset of a ten element set having an odd number of elements.

What we have not shown is that every subset of a ten element set having an odd number of elements has been produced in this way. So, if a subset of a ten element set having an odd number of elements does not contain $$x$$, it is a subset of the nine element set, so is included in the count above. If a subset of a ten element set having an odd number of elements does contain $$x$$, deleting $$x$$ from that subset yields a subset of the nine element set having an even number of elements, so is included in the count above.

Suppose you pick a set a subset $$X$$ from $$\{1,2,\cdots ,10\},$$ construct the following function. If $$10\in X,$$ produce $$Y=X\setminus \{10\}.$$ If $$10\not \in X,$$ then make $$Y=X\cup \{10\}.$$ This is a bijection in between the subsets of odd size and the ones of even size. And so doing odds or even gives the same result and you know that doing evens and odds are $$\sum _{i=0}^{10}\binom{10}{i}=2^{10}.$$ So it has to be half of it. Meaning $$2^9.$$

If this combinatorial thing does not satisfies you, apply binomial theorem to $$(1-1)^{10}.$$ and separate positive and negative elements. What do you get?

The number of sets with odd power is the same as the number of sets with even power. So, since the number of all (sub)sets is $$2^n$$ the answer is $$2^{n-1}$$.