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)$$
Best Answer
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?