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?
Best Answer
There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$ for $\omega$ a primitive $r$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.
They show that both sides count the number of closed $n$-walks on $C_r$ beginning at vertex 0, where $C_r$ is the directed cycle on $r$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.
Left-hand side: In order for an $n$-walk to be closed, it has to take $kr$ forward moves and $n-kr$ stationary moves for some $k$.
Right-hand side: The number of closed walks starting at vertex $j$ is the same regardless of the choice of $j$, and so it suffices to prove that the total number of closed $n$-walks on $C_r$ is $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ For each $n$-walk with initial vertex $j$, assign each forward step a weight of $\omega^j$ and each stationary step a weight of $1$. Define the weight of an $n$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $n$-walks starting at $j$ is $(1+\omega^j)^n$, and $\sum_{j=0}^{r-1} (1+\omega^j)^n$ gives the total weight of all $n$-walks on $C_r$. The open $n$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $0$. Thus the open $n$-walks contribute a total of $0$ to the sum $\sum_{j=0}^{r-1} (1+\omega^j)^n$. Since a closed $n$-walk has weight $1$, $\sum_{j=0}^{r-1} (1+\omega^j)^n$ must therefore give the number of closed $n$-walks on $C_r$.
They then make a slight modification of the argument above to give a combinatorial proof of $$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$ where $0 \leq a < r$.
Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $\sum_{k \geq 0} \binom{n}{3k}$ and $\sum_{k \geq 0} \binom{n}{4k}$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.