# How many non empty subsets of {1, 2, …, n} satisfy that the sum of their elements is even?

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?

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.

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

What you did is fine, we can get an alternative proof if we recall how we prove that there are $2^{n-1}$ subsets of $\{1,2\dots n\}$ of even cardinality.

Let $E$ be the set of subsets of even cardinity and let $O$ be the set of subsets of odd cardinality, pick an arbitrary element $a\in\{1,2,3\dots n\}$.

Then $f:E\rightarrow O$ defined as $X\mapsto \{a\}\Delta X$ is a bijection right?

Well, if $E'$ is the set of subsets with even sum and $O'$ is the set of subsets with odd sum and $a\in\{1,2,3\dots n\}$ is odd.

$f:E'\rightarrow O'$ defined as $X\mapsto \{a\}\Delta X$ is also a bijection.

So in any finite subset $A$ of positive integers, exactly half of the subsets have even sum, unless all of the elements of $A$ are even, in which case all the subsets clearly have even sum.

$\Delta$ is just the symmetric difference of sets, so $\{a\}\Delta X$ is $\{a\}\cup X$ if $a$ was not in $X$ and is $X\setminus\{a\}$ if $a$ was in $X$.