1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's so simple.., $\endgroup$ – Aemilius Feb 23 '18 at 19:37
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.