Prove that if S is a nonempty finite set then S has just as

Prove that if S is a non-empty finite set then S has just as many subsets with an even number of elements as with an odd number.

Solution

here are several ways of proving this for non-empty finite set S. One way is to
let x be an element of S. Now choose any even subset of S; if x is an element
of this subset then removing x will create an odd subset of S, and if x is not an
element of the initial subset then adding x will create an odd subset of S.
Similarly if we to start with an odd subset of S. In this way we create a bijection
between the even and odd subsets of S, which implies that there are an equal
number of odd and even sized subsets.

A more technical approach is to look at the following binomial distribution:

0 = (1 - 1)^n = sum(k=0 to n)((n C k)*(1^(n-k))*((-1)^k)) =

sum(k=0 to n)(((-1)^k)*(n C k) =

sum(all even k up to n)((n C k)) - sum(all odd k up to n)((n C k))

This can be interpreted as

(the number of even sized subsets of a set with n elements) minus

(the number of odd sized subsets of a set with n elements) = 0, and thus the

number of even sized subsets is the same as the number of odd sized subsets.

OR

This is only true if |S| >= 1, so we have to assume that S is not empty. (The empty set has only one subset, with an even number of elements, 0.)

If |S| is odd, then every odd sized set is the complement of an even sized set, so there is a 1-1 correspondence between them. Therefore the number of odd set = the number of even sets.

If |S| is even (and >=2) , pick an s in S and look at S* = S - {s}.
S* has an odd number of elements.
We have
A = the number of odd subsets of S without s
= the number of even subsets of S without s
= the number of odd or even sets of S*

How many odd subsets does S have with s? It\'s A. You get those sets by taking the even subsets of S* and adding s.
How many even subsets does S have with s? It\'s also A. You get those by taking the odd subsets of S* and adding s.

Since a subset of S either has s or doesn\'t, we\'ve looked at all the subsets, and found that there are 2A that are odd, and 2A that are even.