Calculating $ \sum_{k=0}{n\choose 4k+1}$ Calculate $$\sum_{k=0}{n\choose 4k+1}$$
This should be an easy and short result but I'm messing up somewhere. What I've done so far is take $f(x)=(1+x)^n$ and with the binomial theorem expand $f(1), f(-1), f(i), f(-i)$ but it leads to taking cases for n's division rest to 4 (which is too long, $\displaystyle \sum_{k=0}{n\choose 4k}$ is much shorter to calculate). The sum should be, I think, $$\frac{1}{2}\left(2^{n-1}+2^{\frac{n}{2}}\sin\left(\frac{n\pi}{4}\right)\right)$$
 A: For $j = 0,1,2,3$, let $S_j = \displaystyle\sum_{k}\dbinom{n}{4k+j}$. Then, we have
\begin{align*}
2^n = (1+1)^n &= \sum_{\ell}\dbinom{n}{\ell} = S_0+S_1+S_2+S_3
\\
2^{n/2}(\cos\tfrac{n\pi}{4} + i\sin\tfrac{n\pi}{4}) = (1+i)^n &= \sum_{\ell}\dbinom{n}{\ell}i^{\ell} = S_0+iS_1-S_2-iS_3
\\
0 = (1-1)^n &= \sum_{\ell}\dbinom{n}{\ell}(-1)^{\ell} = S_0-S_1+S_2-S_3
\\
2^{n/2}(\cos\tfrac{n\pi}{4} - i\sin\tfrac{n\pi}{4}) = (1-i)^n &= \sum_{\ell}\dbinom{n}{\ell}(-i)^{\ell} = S_0-iS_1-S_2+iS_3
\end{align*}
Equation 1 minus Equation 3 gives $$2^{n} = 2S_1+2S_3,$$ and Equation 2 minus Equation 4 gives $$2^{n/2+1}i\sin\tfrac{n\pi}{4} = 2iS_1-2iS_3.$$ Can you take it from here?
A: In case there is interest we can also do this one with residues, by way
of enrichment, and demonstrate some complex arithmetic. Start with
$$\sum_{k\ge 0} {n\choose 4k+1}
= \sum_{k\ge 0} {n\choose n-4k-1}
= [z^{n-1}] (1+z)^n \sum_{k\ge 0} z^{4k}
\\ = [z^{n-1}] (1+z)^n \frac{1}{1-z^4}
= \mathrm{Res}_{z=0} \frac{1}{z^n}
(1+z)^n \frac{1}{1-z^4}.$$
Now residues sum to zero and the residue at infinity is zero by
inspection. This leaves the residues at $\rho_m = \exp(m \pi i/2)$
where $0\le m\lt 4.$ We obtain for our sum (using the fact that the
poles are simple)
$$- \sum_\rho \mathrm{Res}_{z=\rho}
\frac{1}{z^n} (1+z)^n \frac{1}{1-z^4}
\\ = - \sum_\rho
\frac{1}{\rho^n} (1+\rho)^n
\lim_{z\rightarrow \rho}
\frac{z-\rho}{(1-z^4)-(1-\rho^4)}
\\ = - \sum_\rho
\frac{1}{\rho^n} (1+\rho)^n
\frac{1}{-4\rho^3}
= \frac{1}{4} \sum_\rho
\frac{1}{\rho^{n+3}} (1+\rho)^n
= \frac{1}{4} \sum_\rho
\frac{\rho}{\rho^{n}} (1+\rho)^n.$$
Expanding with $(1+\rho)/\rho = 1 + 1/\rho$, we get
$$\frac{1}{4} \times 1  \times  2^n
+ \frac{1}{4} \times i  \times  (1-i)^n
+ \frac{1}{4} \times -1 \times  0^n
+ \frac{1}{4} \times -i \times  (1+i)^n
\\ = \frac{1}{4} 2^n +
\frac{1}{4} i \sqrt{2}^n
(\exp(-i\pi n/4)-\exp(i\pi n/4))
\\ = \frac{1}{4} 2^n
- \frac{1}{2} \sqrt{2}^n
\frac{\exp(-i\pi n/4)-\exp(i\pi n/4)}{2i}
\\ = \frac{1}{4} 2^n
- \frac{1}{2} \sqrt{2}^n \sin(-\pi n/4)
= \frac{1}{2} (2^{n-1} + 2^{n/2} \sin(\pi n/4)).$$
This is the claim.
