Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.

I know that the number of elements of the power set of $A$ is $2^n$, i.e. $|\mathcal{P}(A)|=2^n$.

I came across the fact that exactly half of the elements of $\mathcal{P}(A)$ contain an odd number of elements, and half of them an even number of elements.

Can someone prove this? Or hint at a proof?

share|improve this question
3  
A nice proof goes by using the binomial theorem: $(x+y)^n=\sum_k \binom{n}k x^k y^{n-k}$. Here, $\binom{n}{k}$ is the number of $k$-sized subsets of a set of size $n$. Your result corresponds to the fact that $0=(1-1)^n$. Expanding, the binomial theorem gives us that the sum of the $\binom{n}{k}$ with $k$ odd equals the sum of the $\binom{n}{k}$ with $k$ even. The first is precisely the number of odd-sized subsets, and the second is the number of even-sized subsets. –  Andres Caicedo Nov 30 '12 at 20:14
1  
I'm amazed at the fact that you guys answer so quickly! Thanks and wow! –  gbag Nov 30 '12 at 20:18
    
I'm amazed that so many people bothered to write answers, and that there are some good answers, but there is only one upvote to the question. –  Asaf Karagila Nov 30 '12 at 20:29

7 Answers 7

up vote 18 down vote accepted

Fix an element $a\in A$ (this is the point where $A\ne\emptyset$ is needed). Then $$S\mapsto S\operatorname{\Delta}\{a\}$$ (symmetric difference) is a bijection from the set of odd subsets to the set of even subsets.

share|improve this answer
    
Very nice! ${}{}{}$ –  Asaf Karagila Nov 30 '12 at 20:29
1  
Indeed, really cute! –  Peter Smith Nov 30 '12 at 20:51

Hint: One can prove this by induction on the size of $A$. Assume it was true for sets of size $n$ and let $A=\{a_1,\ldots,a_{n+1}\}$. Then every subset of $A$ is either a subset of $\{a_1,\ldots,a_n\}$ or it is a copy of such subset with the addition of $\{a_{n+1}\}$. Use the induction hypothesis to conclude that the sets which do not contain $a_{n+1}$ have this property (with respect to $\{a_1,\ldots,a_n\}$, by adding $a_{n+1}$ you send exactly the same number of odd sets to even size sets, and vice versa; therefore the ratio remains true for $A$.

share|improve this answer

Suppose $n=|A|$. Then there are $$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}=2^{n-1}$$ sets with even cardinality. Thus, there are exactly half of the sets with an even number of elements.

share|improve this answer
    
For me, it's not obvious why this identity holds. Could you maybe elaborate? –  gbag Nov 30 '12 at 20:23
    
It's easiest to prove by induction. If n=1, then there is exactly 1 set with an even number of elements: the set with no elements (the empty set). Suppose it's true for some positive integer k. Then k+1 is either odd or even. If it's odd, then the floor of (k+1)/2=k/2, in which case we're done. If it is even, then break up the sum and binomial coefficient, combine, and you get the desired result. –  Clayton Nov 30 '12 at 20:44

For $n\in\Bbb Z^+$ let $[n]=\{1,2,\dots,n\}$. Clearly $[1]$ has one even subset and one odd subset. Suppose that $[n]$ has equal numbers of odd and even subsets for some $n\in\Bbb Z^+$. The even subsets of $[n+1]$ are of two types:

  • the even subsets of $[n]$; and
  • the sets of the form $A\cup\{n+1\}$, where $A$ is an odd subset of $[n]$.

By the induction hypotheses there are the same number of sets of the second type as there are of the first, so $[n+1]$ has twice as many even subsets as $[n]$. But $[n+1]$ also has twice as many subsets altogether as $[n]$, so it must have twice as many odd subsets as well, which clearly implies that it has equal numbers of odd and even subsets.

share|improve this answer
2  
+1 but you do not even need the induction hypothesis, as you have shown that the number of even subsets of $[n+1]$ is equal to the number of subsets of $[n]$ and a very similar argument would show the number of odd subsets of $[n+1]$ is the same. –  Henry Dec 1 '12 at 2:53

When $n$ is odd, look at each set and its complement: one will have even number of elements and the other, odd (because odd number can only be written as a sum of an odd and an even number).

When $n$ is even, remove an element to obtain a set with odd number of elements. By the first part, half of its subsets have even cardinality and half odd. Now to form the full $\mathcal P(A)$, we need to join the remainin element to each of the previous subsets: those with odd cardinality with become even, and viceversa.

share|improve this answer

You can use proprieties of the binomial coefficients.

Denote $\mathcal{P}_k(A)$ the family of subsets of $A$ containing $k$ elements and observe $|\mathcal{P}_k(A)| = {n \choose k}$ .

Now by a propriety of binomial coefficients $\sum_{k=0}^{n/2} {n \choose 2k} =\sum_{k=0}^{n/2} ({n-1 \choose 2k-1} + {n-1 \choose 2k}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ and similarly $\sum_{k=0}^{n/2-1} {n \choose 2k+1} =\sum_{k=0}^{n/2-1} ({n-1 \choose 2k} + {n-1 \choose 2k+1}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ .

This shows that $\sum_{k=0}^{n/2}|\mathcal{P}_{2k}(A)| = \sum_{k=0}^{n/2-1}|\mathcal{P}_{2k+1}(A)|$ .

share|improve this answer

Number the members of the set $1,2,3,4,\ldots,n$.

For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:

  • If $1$ is a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements.
  • If $1$ is not a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.

For example, suppose the set is $\{1,2,3,4\}$. Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements: $$ \begin{array}{rcl} \text{even} & & \text{odd} \\ \hline \varnothing & \leftrightarrow & \{1\} \\ \{1,2\} & \leftrightarrow & \{2\} \\ \{1,3\} & \leftrightarrow & \{3\} \\ \{1,4\} & \leftrightarrow & \{4\} \\ \{2,3\} & \leftrightarrow & \{1,2,3\} \\ \{2,4\} & \leftrightarrow & \{1,2,4\} \\ \{3,4\} & \leftrightarrow & \{1,3,4\} \\ \{1,2,3,4\} & \leftrightarrow & \{2,3,4\} \end{array} $$

This won't work with the empty set because we don't have an element to which we can assign the number $1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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