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.

The question I am working on is the case for $n$ = 9. How many non-empty subsets of $\{1,2,...,9\}$ have that the sum of their elements is even?

My solution is that the sum of elements is even if and only if the subset contains an even number of odd numbers. Since this is precisely half of all of the subsets the answer is $\frac{2^{9}}{2}=2^8$. Then the question specifies non-empty so final answer is $2^8-1$. Is this correct? In general I guess the solutions is $2^{n}-1$. My problem is why do exactly half of the total amount of subsets have and even number of odd numbers? Can we set up a bijection between subsets with odd number of odd numbers and even number of odd numbers?

share|improve this question

2 Answers 2

up vote 8 down vote accepted

Let $S$ be a subset of $\{0,1,2,\dots,9\}$, possibly empty. Note that $1+2+\cdots +9=45$. So the sum of the elements of $S$ is even if and only if the sum of the elements of the complement of $S$ is odd.

Divide the subsets of $\{1,2,\dots,9\}$ into complementary pairs. There are $2^8$ such pairs, and exactly one element of each pair has even sum. Thus there are $2^8$ subsets with even sum, and $2^8-1$ if we exclude the empty set.

Remark: Suppose that $1+2+\cdots+n$ is odd. This is the case when $n\equiv 1\pmod{4}$ and when $n\equiv 2\pmod{4}$. Then the same argument shows that there are $2^{n-1}$ subsets with even sum.

We can use another argument for the general case. Note that there are just as many subsets of $\{1,2,\dots,n\}$ that contain $1$ as there are subsets that do not contain $1$. And for any subset of $A$ of $\{2,3,\dots,n\}$, we have that $A$ has even sum if and only if $A\cup\{1\}$ has odd sum, and $A$ has odd sum if and only if $A\cup\{1\}$ has even sum. Thus in general there are $2^{n-1}$ subsets with even sum.

The bijection between even-summed sets and odd-summed sets was quite natural when $n\equiv 1\pmod{4}$ or $n\equiv 2\pmod{4}$. In the general case, there is a nice bijection (add or subtract $\{1\}$), but it is less natural.

share|improve this answer

Let's first count all subsets of $\{1,\ldots,n\}$ with even sum. Removing the empty sets then makes us have to subtract one from this result.

The subsets of $\{1,\ldots,n\}$ with even sum are one-to-one with the subsets of $\{2,\ldots,n\}$. For any set $J\subset\{2,\ldots,n\}$, if the sum of $J$ is even, then $J$ is a subset of $\{1,\ldots,n\}$ with even sum, while if the sum of $J$ is odd, then $\{1\}\cup J$ is a subset with even sum.

Since there are $2^{n-1}$ subsets of $\{2,\ldots,n\}$, this is the number of subsets of $\{1,\ldots,n\}$ with even sum. Remove the empty set, and you get $2^{n-1}-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.