Calculating $ \sum_{k=0}{n\choose 4k+1}$

Question

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)$$

Answer 1

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?

Answer 2

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.