# 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:

1. $$A, B \in T$$
2. $$A, B \notin T$$
3. Only $$A \in T$$
4. 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:

1. $$|T| = 4k$$. Teams of this kind correspond to teams of size $$4k$$ that don't contain $$A$$ and $$B$$.
2. $$|T| = 4k + 1$$. Teams of this kind will just be discarded.
3. $$|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$$.
4. $$|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.

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}

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\}$$