Can anybody help me solve this combinatorial identity? While trying to derive some physical equation, I noticed that the following identity was needed:
$\sum^{4a \leq 2k}_{a=0}{2k \choose 4a} + \sum^{4a+1 \leq 2k}_{a=0} {2k \choose 4a+1} = \left\{ \begin{array}{ll} \frac{2^k(2^k +1)}{2} & (k=4l+1, 4l+4)\\
                          \frac{2^k(2^k -1)}{2} & (k=4l+2, 4l+3) \end{array} \right.$
(where $l,a$ are positive integers) 
My strategy was to change  the $2^k$'s of RHS into $\sum_{a=0}^{a=k}{k \choose a}$ and use ${n \choose k}={n-1 \choose k} +{n-1 \choose k-1}$, but obtained only incomplete and partial relations. Can anybody solve this identity explicitly, or at least suggest another strategy that might work better? 
 A: This is just a rephrasing of André Nicolas' answer, I put it here just because I was typing it when his answer suddenly appeared.
The Discrete Fourier Transform gives:
$$ 1^k+i^k+(-1)^k+(-i)^k = 4\cdot\mathbb{1}_{k\equiv 0\pmod{4}} \tag{1}$$
hence:
$$ \mathbb{1}_{k\equiv 0,1\pmod{4}} = \frac{1}{4}\left(2+(1-i)\,i^k+(1+i)\,(-i)^k\right)\tag{2}$$
and:
$$\begin{eqnarray*}\sum_{\substack{0\leq a\leq 2k\\ a\equiv{0,1}\pmod{4}}}\!\!\!\!\!\binom{2k}{a}&=&\sum_{a=0}^{2k}\binom{2k}{a}\mathbb{1}_{a\equiv 0,1\pmod{4}}\\&=&\frac{1}{2}\left(2^{2k}+(1+i)^{2k-1}+(1-i)^{2k-1}\right)\end{eqnarray*}\tag{3}$$
hence the claim follows by considering that $(1+i)$ is $\sqrt{2}$ times an eigth root of unity, $e^{\frac{\pi i}{4}}$.
A: A tool: By the Binomial Theorem, we have 
$$(1+x)^n=1+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\binom{n}{5}x^5+\cdots. \tag{1}.$$ Putting $x=1$ we get a familiar identity, and putting $x=-1$ we get something almost as familiar. 
Using addition and subtraction, we get the sum of the binomial coefficients of the shape $\binom{n}{k}$, where $k$ ranges over the even numbers, and also the sum where $k$ ranges over the odd numbers.
Now comes the interesting part. Put $x=i$. We get
$$(1+i)^n=1+\binom{n}{1}i-\binom{n}{2}^2-\binom{n}{3}i+\binom{n}{4}+\binom{n}{5}i+\cdots \tag{2}.$$
We get a similar result by using $x=-i$. It can also be obtained from (2) by conjugation. 
We connect Equation (2) with powers of $2$. Note that $1+i=\frac{1}{\sqrt{2}}\left(\cos(\pi/4)+i\sin(\pi/4)\right)$. Taking the $n$-th power, we get 
$(1+i)^n=2^{n/2}\left(\cos(n\pi/4)+i\sin(n\pi/4)\right)$. Do the same with the substitution $x=1-i$.  By taking real and imaginary parts, we get explicit formulas for sums of certain types of binomial coefficients. 
By playing with the ideas above, we can get explicit formulas for $\sum \binom{n}{k}$, where (i) $k$ ranges over multiples of $4$; (ii) $k$ ranges over the numbers that have remainder $1$ on division by $4$; $k$ ranges over the numbers with remainder $2$ on division by $4$; (iv) $k$ ranges over the numbers with remainder $3$. 
For remainder $0$ or $1$ (your problem) one may not need remainder $0$ and remainder $1$ separately. 
