0
$\begingroup$

Given a set of cardinality $n\geq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality

I am looking for a combinatorial proof of this statement- I know an algebraic proof is easy, for instance by expanding $(1-1)^n$. If $n$ is odd it is easy to see there is a one-to-one correspondence between even-cardinality subsets an odd-cardinality subsets using the complement. However, I can't think of a combinatorial proof if $n$ is even. Any ideas?

$\endgroup$
1
$\begingroup$

Just pick your favourite element $a$. Now take a subset $X$ and add $a$ if $a\notin X$ and delete it if $a\in X$. One gets a pairing of the subsets, and in each pair one subset is even, the other odd.

$\endgroup$
0
$\begingroup$

use the case for odd $n$, and consider adding a single additional element to the set. the old subsets are still subsets, together with new ones which contain the additional element.

$\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.