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

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