<s>[INST] 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)$$
 [/INST] 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.
</s>