Number of subsets of $[n]$ in which sum of their elements is divisible by 4 Intuitively it is clear that the answer is $1/4$ of all subsets
I also know that I can solve it with two bijections.
Let S(A) be sum of elements of any subset
If S(A) is even  we add 1 to S(A)
If S(A) is odd we subtract 1
Then we have bijection between subsets with even sum and subsets with odd sum.
Now we construct similar bijection between subsets with even sum which are divisible by 4 and subsets which are not (by adding and subtracting 2)
However I'm listening to combinatorics for the first time and I'm having trouble writing the formal proof
 A: Proof it is $1/4$ of all the subsets when $n\geq 2$:
Notice that for the set $\{1,2\}$ there is $1$ sum for each congruence $\bmod 4$.
It follows that for every set that contains $1$ and $2$ there is exactly $1/4$ for each congruence $\bmod 4$.
This is because if $X = A \cup \{1,2\}$ where $A$ and $\{1,2\}$ are disjoint then for each $B\subseteq A$ the sets $B,B\cup\{1\},B\cup\{2\},B\cup\{1,2\}$ are in different congruence classes.
A: Here is the outline of an approach based on generating functions.  First, let $\sigma(S)$ denote the sum of the elements of $S$.  Then
$$\sum_{S \subseteq [n]} x^{\sigma(S)} = (1 + x) (1 + x^2) \cdots (1 + x^n).$$
Here, the factor $1 + x^k$ represents the choice of whether $k$ is in the subset or not.
Now, suppose we let $a_0, a_1, a_2, a_3$ denote the number of subsets of $[n]$ such that $\sigma(S) \equiv 0, 1, 2, 3 \pmod{4}$ respectively.  Then if we substitute $x := 1$ in the above equation, we see that
$$a_0 + a_1 + a_2 + a_3 = 2^n.$$
(Of course, this is trivial to see combinatorially.)  Similarly, if we substitute $x := -1$ and we have that $n \ge 1$ (so that $1 + x = 0$), then
$$a_0 - a_1 + a_2 - a_3 = 0.$$
And then, if we substitute $x := i$ and we have that $n \ge 2$ (so that $1 + x^2 = 0$), then
$$a_0 + i a_1 - a_2 - i a_3 = 0.$$
Taking the real and imaginary parts respectively, we get that $a_0 - a_2 = a_1 - a_3 = 0$.  Now, these conditions are sufficient to imply that if $n \ge 2$, then
$$a_0 = a_1 = a_2 = a_3 = 2^{n-2}.$$
And the original question asked for the value of $a_0$.
