# Prove that every $n$-element set has the same number of subsets with even and odd cardinality without creating a bijection

I need to prove that the number of even and odd subsets of a finite set if always equal. This is not a problem once we assume that $n$ is odd. Then, every "even" subset of the set defines in a unique way an "odd" subset and vice versa.
The problem starts once we assume that $n$ is even. The argument used in the previous case no longer works. I read some answers on Stack, but each of them, at this point, constructed a bijection which looked strange to me.
Is there a combinatorial or algebraical way to prove this theorem?

A bijection is a combinatorial way IMO. But there's a simple inductive argument. It's true for $n=1;$ suppose true for $n$ and take a set $S$ of size $n+1.$ Let $a$ be any element of $S$. Now $S- a$ is a set of size $n$, so has the same number of odd and even subsets. Therefore $S$ has the same number of odd subsets not containing $a$ as it has even subsets not containing $a.$ By adding $a$ to each subset, it also has the same number of even subsets containing $a$ as odd subsets containing $a.$ So in total it has the same number of odd and even subsets.

Give each size-$k$ subset a score of $(-1)^k$. The result you want is that the sum of all subsets' scores is $0$. But we can factorise that sum as $(1+(-1))^n$, since each element is either in or not in a subset, and multiplies the empty set's score of $1$ by $-1$ if it's included.

• That's so simple.., – Aemilius Feb 23 '18 at 19:37

The number of elements in $P(S)$ is $2^n$. Suppose that $P_o(S) = 2^{n-1} = P_e(S)$ for all $1 \leq n \leq N$. Then the sets are $P(S \cup a) = P(S) \cup (a \cup P(S))$. Thus there are $2^{n-1} + \#\{ a \cup A : A \in P(S), |A| \text{ odd}\}$ even elements, and similarly for odd. Proof by induction.

Here's my way of thinking... A set of cardinality $n$ will have $2^n$ subsets (why?)

Suppose that, for some $n$, the number of even and odd subsets is the same, i.e. $x$ for some $x$. Then $2x=2^n$.

Now suppose I introduce a new element, so we have a set of cardinality $n+1$. All the even subsets of the original $n$ items are still even subsets of our new slightly larger set - so we have $x$ even subsets AND all of the odd subsets of $n$ can be made into even subsets of $n+1$ by including our new element - and so we have another $x$ even subsets, giving $2x$ even subsets. However, we know that $2x=2^n=\frac{1}{2} \times 2^{n+1}$ and so exactly half of the subsets of our new set are even (implying the other half are odd). This is the inductive step in a proof by induction, you now just need to find an $n$ such that the base step holds (hint, $n=1$ might be worth a go).