Solution to Let S be a finite nonempty set. Show that the number of subsets of S … - Sikademy
Author Image

Archangel Macsika

Let S be a finite nonempty set. Show that the number of subsets of S of even cardinality equals the number of subsets of S of odd cardinality.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Let |S|=n. In total there are 2^n subsets of S.


If n is odd then there is a one-to-one correspondence between sets with even cardinality and sets with odd cardinality. Subset A corresponds with its complement S\setminus A. Consequently, the number of subsets with even cardinality equals the number of subsets with odd cardinality. So this number is \frac{1}{2}2^n=2^{n-1}.


If n is even then put one element a\in S aside. With the trick described above we find that S\setminus\{a\}  has 2^{n-2} subsets with even cardinality and also 2^{n-2} subsets with odd cardinality. The subsets of S\setminus\{a\}  with odd cardinality become subsets S  with even cardinality if element a is added to each of them. This gives us 2^{n-2}+2^{n-2}=2^{n-1} subsets of S with even cardinality. So in both cases the number of subsets of S of even cardinality equals the number of subsets of S of odd cardinality.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3579-qpid-2278