Proving the identity of $\sum_{k = 0}^n{4n \choose 4k} = 2^{4n - 2} + (-1)^n2^{2n - 1}$ combinatorially

Question

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.

Answer 1

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}

Answer 2

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