Count subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively Given a set of N elements, compute the number of subsets whose cardinalities are congruent to 0, 1 and 2 modulo 3 respectively.
Any hints would be appreciated. 
Thanks!
 A: You want to evaluate
 \begin{align}a_N=\binom N0+\binom N3+\binom N6+\binom N9+\cdots,\\b_N=\binom N1+\binom N4+\binom N7+\binom N{10}+\cdots,\\c_N=\binom N2+\binom N5+\binom N8+\binom N{11}+\cdots.\end{align}
 Note that, if $x^3=1$, then
 \begin{align} (1+x)^N&=\binom N0+\binom N1x+\binom N2x^2+\binom N3x^3+\binom N4x^4+\binom N5x^5+\cdots\\&=\binom N0+\binom N1x+\binom N2x^2+\binom N3+\binom N4x+\binom N5x^2+\cdots\\&=a_N+b_Nx+c_Nx^2.\end{align}
 So write down the equation
 \begin{align}a_N+xb_N+x^2c_N=(1+x)^N\end{align}
 with $x$ replaced in turn with each of the three cube roots of unity, and solve the resulting system of three linear equations for the three unknowns $a_N, b_N, c_N$.
The cube roots of unity are $1$, $\omega=\cos\frac{2\pi}3+i\sin\frac{2\pi}3$, and $\omega^2=\bar\omega$, so the equations are
$$a_N+b_N+c_N=2^N;$$
$$a_N+\omega b_N+\omega^2c_N=(1+\omega)^N;$$
$$a_N+\omega^2b_N+\omega c_N=(1+\bar\omega)^N.$$
To solve for $a_N$ we add all the equations and divide by $3$; since $1+\omega+\omega^2=0$ we get
$$a_N=\frac{2^N+(1+\omega)^N+(1+\bar\omega)^N}3=\frac{2^N+2\Re(1+\omega)^N}3.$$
Since $(1+\omega)^N=(\cos\frac\pi3+i\sin\frac\pi3)^N=\cos\frac{N\pi}3+i\sin\frac{N\pi}3$, this simplifies to
$$a_N=\frac{2^N+2\cos\frac{N\pi}3}3.$$
In like manner, we get
$$b_N=\frac{2^N-\cos\frac{N\pi}3+\sqrt{3}\sin\frac{N\pi}3}3$$
and
$$c_N=\frac{2^N-\cos\frac{N\pi}3-\sqrt{3}\sin\frac{N\pi}3}3.$$
Alternatively, use Pascal's identity $\binom Nk=\binom{N-1}k+\binom{N-1}{k-1}$ to derive the linear recurrences $a_N=a_{N-1}+c_{N-1},b_N=b_{N-1}+a_{N-1},c_N=c_{N-1}+b_{N-1}$ with initial values $a_0=1,b_0=c_0=0$. As an alternative to the matrix method, you could use the guess-and-check method: calculate a few values, observe the simple pattern, and verify by induction.
A: Hint:
$\sum_{k\in\mathbb{Z}}\binom{N}{3k}$ , $\sum_{k\in\mathbb{Z}}\binom{N}{3k+1}$
and $\sum_{k\in\mathbb{Z}}\binom{N}{3k+2}$ respectively.
This under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,\dots,n\right\} $.
