Counting subsets of a set with $n$ elements

219 Views Asked by At

I am trying to understand a proposition from my textbook, which is the following: Let $n \ge 1.$ Every set with n elements has $2^{n-1}$ subsets with an uneven number of elements and equally many subsets with an even number of elements.

Prove: Let X be a set with n elements and $ a \in X$ be a defined element. In this case $X \setminus \{a\}$ has $2^{n-1}$ subsets, since a set of n elements has $2^n$ subsets. A subset of $X \setminus \{a\}$ contains either an uneven, or an even number of elements. On the other hand, every uneven subset does or does not contain a.

All of this is pretty clear to me, but it's the next part that I don't get: It follows that X has exactly $2^n-1$ uneven subsets and $2^n-2^{n-1}=2^{n-1}$ subsets.

Question: Why is $2^n-2^{n-1}=2^{n-1}$ in this?

Thank you for any help given!

2

There are 2 best solutions below

1
On BEST ANSWER

$2^n$ = $2 * 2^{n-1}$

$2 \cdot 2^{n-1}-2^{n-1}=2^{n-1}$

0
On

Note that $$2^n-2^{n-1}= 2\cdot 2^{n-1} - 1\cdot 2^{n-1} = 2^{n-1}(2-1)=2^{n-1}$$