Proving the identity of $\sum_{k = 0}^n{4n \choose 4k} = 2^{4n - 2} + (-1)^n2^{2n - 1}$ combinatorially I want to prove the following identity combinatorially:
$$\sum_{k = 0}^n{4n \choose 4k} = 2^{4n - 2} + (-1)^n2^{2n - 1}$$
Here's my attempt so far: The left hand side is counting the number of teams among $4n$ people where the size of the team is a multiple of 4. Now let $A$ and $B$ be the last two people among these $4n$ people. Now let $T$ be a team such that $|T| = 4k$. Then we have 4 cases:

*

*$A, B \in T$

*$A, B \notin T$

*Only $A \in T$

*Only $B \in T$
Now I will construct all teams among the $4n - 2$ people after removing $A$ and $B$ (I don't care about their size) and convert them to a team of size $4k$ by adding a subset of $\{A, B\}$ to them. Clearly there are $2^{4n - 2}$ teams that don't contain $A$ or $B$. Let $T$ be one of these teams. Then we have the following cases:

*

*$|T| = 4k$. Teams of this kind correspond to teams of size $4k$ that don't contain $A$ and $B$.

*$|T| = 4k + 1$. Teams of this kind will just be discarded.

*$|T| = 4k + 2$. Teams of this kind correspond to teams of size $4k'$ that contain both $A$ and $B$. We will just add $A$ and $B$ to $T$.

*$|T| = 4k + 3$. Teams of this kind will be converted to teams of size $k'$ that contain either $A$ or $B$. Then for each team of this kind, we should add $1$ to $2^{4n - 2}$ because we have 2 cases here. Either add $A$ or add $B$.

Based on these cases, we will have $2^{4n - 2} - \sum_{i = 0}^{n - 1}{4n - 2 \choose 4i + 1} + \sum_{i = 0}^{n - 2}{4n - 2 \choose 4i + 3}$. If I've made no mistakes, then I should show that $- \sum_{i = 0}^{n - 1}{4n - 2 \choose 4i + 1} + \sum_{i = 0}^{n - 2}{4n - 2 \choose 4i + 3} = (-1)^n2^{2n - 1}$ but I don't know how to do this.
 A: Here's an indirect approach that works.
First prove combinatorially that
$$(x-1)(1+x+x^2+\dots+x^{n-1}) = x^n - 1 \quad \text{for $n \ge 1$},$$
which is Identity 216 in Proofs That Really Count: The Art of Combinatorial Proof.
Then take $n=4$ and $x=i^k$ to yield
$$\frac{(i^k)^0+(i^k)^1+(i^k)^2+(i^k)^3}{4} = \begin{cases}1 & \text{if $4 \mid k$} \\ 0 & \text{otherwise}\end{cases}$$
and so
$$\sum_{k \ge 0}^n a_{4k} = \sum_{k \ge 0} \frac{1+i^k+(-1)^k+(-i)^k}{4} a_k.$$
Now take $a_k = \binom{4n}{k}$ and apply the binomial theorem, which has a clear combinatorial proof, to obtain
\begin{align}
\sum_{k \ge 0}^n \binom{4n}{4k} 
&= \sum_{k \ge 0} \frac{1+i^k+(-1)^k+(-i)^k}{4} \binom{4n}{k} \\
&= \frac{1}{4} \sum_{k \ge 0} \binom{4n}{k} 
 + \frac{1}{4} \sum_{k \ge 0} i^k \binom{4n}{k} 
 + \frac{1}{4} \sum_{k \ge 0} (-1)^k \binom{4n}{k} 
 + \frac{1}{4} \sum_{k \ge 0} (-i)^k \binom{4n}{k} \\
&= \frac{(1+1)^{4n} + (1+i)^{4n} + (1-1)^{4n} + (1-i)^{4n}}{4} \\
&= \frac{2^{4n} + (-4)^n + 0 + (-4)^n}{4} \quad \text{for $n>0$} \\
&= 2^{4n-2} + (-1)^n 2^{2n-1}.
\end{align}
A: I don't know the combinatorial answer to this question, at least not fully. But here is how I would solve this:
Define $n_{i}$ as the number of subsets of $\{1,...,4n\}$ such that the number of elements in the subset is $i$ in modulo $4$.

*

*The number of subsets with even number of elements is $2^{4n-1}$, so $n_{0}+n_{2}=2^{4n-1}$.

*The difference $n_{0}-n_{2}$ is given by the real part of $(1+i)^{4n}$, which is $(-1)^{n}\phantom{.}2^{2n}$
Therefore we get $n_{0}=\frac{2^{4n-1}+(-1)^{n}\phantom{.}2^{2n}}{2}=2^{4n-2}+(-1)^{n}\phantom{.}2^{2n-1}$


Regarding the combinatorial proof, I cannot get my mind off the fact that if $m=2^{2n-1}$ then the term on the right hand side of your equation is $2\binom{m}{2}$ if $n$ is even or $2\binom{m+1}{2}$ if $n$ is odd. $m$ can be interpreted as the number subsets with even (or odd) number of elements from $\{1,...,2n\}$
