<s>[INST] How do I count the subsets of a set whose number of elements is divisible by 3? 4? Let $S$ be a set of size $n$.  There is an easy way to count the number of subsets with an even number of elements.  Algebraically, it comes from the fact that
$\displaystyle \sum_{k=0}^{n} {n \choose k} = (1 + 1)^n$
while
$\displaystyle \sum_{k=0}^{n} (-1)^k {n \choose k} = (1 - 1)^n$.
It follows that 
$\displaystyle \sum_{k=0}^{n/2} {n \choose 2k} = 2^{n-1}$.  
A direct combinatorial proof is as follows: fix an element $s \in S$.  If a given subset has $s$ in it, add it in; otherwise, take it out.  This defines a bijection between the number of subsets with an even number of elements and the number of subsets with an odd number of elements.
The analogous formulas for the subsets with a number of elements divisible by $3$ or $4$ are more complicated, and divide into cases depending on the residue of $n \bmod 6$ and $n \bmod 8$, respectively.  The algebraic derivations of these formulas are as follows (with $\omega$ a primitive third root of unity):  observe that
$\displaystyle \sum_{k=0}^{n} \omega^k {n \choose k} = (1 + \omega)^n = (-\omega^2)^n$
while
$\displaystyle \sum_{k=0}^{n} \omega^{2k} {n \choose k} = (1 + \omega^2)^n = (-\omega)^n$
and that $1 + \omega^k + \omega^{2k} = 0$ if $k$ is not divisible by $3$ and equals $3$ otherwise.  (This is a special case of the discrete Fourier transform.)  It follows that
$\displaystyle \sum_{k=0}^{n/3} {n \choose 3k} = \frac{2^n + (-\omega)^n + (-\omega)^{2n}}{3}.$
$-\omega$ and $-\omega^2$ are sixth roots of unity, so this formula splits into six cases (or maybe three).  Similar observations about fourth roots of unity show that
$\displaystyle \sum_{k=0}^{n/4} {n \choose 4k} = \frac{2^n + (1+i)^n + (1-i)^n}{4}$
where $1+i = \sqrt{2} e^{ \frac{\pi i}{4} }$ is a scalar multiple of an eighth root of unity, so this formula splits into eight cases (or maybe four).  
Question:  Does anyone know a direct combinatorial proof of these identities? 
 [/INST] I try to add details with simple calculation:
for example, I show $\binom{n}{1}+\binom{n}{3}+\binom{n}{6}+\cdots=\frac{1}{3}[2^n+2\cos(\frac{n\pi}{3})]$
we know $(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n$, so if in this identity we put $1,\alpha,\alpha^2$ where $\alpha=\cos\frac{2\pi}{3}+i\sin(\frac{2\pi}{3})$respectively, then we get $$2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots$$, $$(1+\alpha)^n=\binom{n}{0}+\binom{n}{1}\alpha+\binom{n}{2}\alpha^2+\binom{n}{3}\alpha^3+\cdots$$,
$$(1+\alpha^2)^n=\binom{n}{0}+\binom{n}{1}\alpha^2+\binom{n}{2}\alpha^4+\binom{n}{3}\alpha^6+\cdots$$
but if $3\nmid n$, then we can easily see that $1+\alpha^k+\alpha^{2k}=3$ hence 
$2^n+(1+\alpha)^n+(1+\alpha^2)^n=3\{\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots\}$ but since $1+\alpha+\alpha^{2}=0$ hence
$1+\alpha=-\alpha^2=\cos(\frac{\pi}{3})+i\sin(\frac{\pi}{3})$ and also $1+\alpha^2=-\alpha=\cos(\frac{\pi}{3})-i\sin(\frac{\pi}{3})$ hence $$2^n+(1+\alpha)^n+(1+\alpha^2)^n=2^n+2\cos(\frac{n\pi}{3})$$, so we get the desired result.
</s>