[Math] How many subsets with an odd number of elements does a set with 10 elements have

combinatoricsdiscrete mathematics

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?

Best Answer

One way to see this combinatorially is to consider the $10$ elements in some order. With each of 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$th element, since to ensure the total # of elements in the set is odd, this element must be included if the total # so far is even, and not included if the total # is odd. Thus, since there are $2$ choices for each of the first $9$ elements, this means there are $2^9$ choices overall.