# Sum of binomial coefficients, with alternate signs, congruent two or zero modulo four

I've come across the following formula:

$$S(n) \;:= \sum _{ \begin{array}{c} k=0 \\ k \equiv_4 0,\; 2 \end{array} } ^{ n } 2 \cdot \binom{n}{k}\cdot (-1)^{k \over 2}$$

where the summation run over the values of $$k$$ in $$[0, n]$$ that are congruent modulo 4 to 0 or 2.

Can this be simplified?

I've numerically verified that the sum takes the following values: $$S(n) = \begin{cases} (-1)^{n \over 4} \cdot 2^{{n\over 2} + 1}, & \text{if n \equiv_4 0 } \\ S(n-1) , & \text{if n \equiv_4 1 } \\ 0, & \text{if n \equiv_4 2 } \\ (-1)^{n +1 \over 4} \cdot 2^{n+1\over2}, & \text{if n \equiv_4 3 } \\ \end{cases}$$

but except for the case $$n \equiv_4 2$$ I can see why this is the case.

Particularly interesting, to me, are the fact that this sum is either 0 or a power of two and the case $$n \equiv_4 1$$ where the two partial sums of the binomial coefficients in adjacent rows total the same (e.g. $$2 \cdot 1 - 2 \cdot 6 + 2 \cdot 1 = 2 \cdot 1 - 2 \cdot 10 + 2 \cdot 5$$ for the 5th and 6th row of the Pascal's triangle).

• Two possible simplifications. The sum is over all even $k$; no need to think mod $4$ about the index. You can factor $2$ from the sum. – Ethan Bolker Jan 9 at 17:42

$$S(n)=2\sum_{k\equiv_40,2}^n(-1)^{k/2}\binom nk=2\Big(\binom n0-\binom n2+\binom n4...\Big)$$
Consider $$(1+x)^n=\binom n0+\binom n1x+\binom n2x^2+...+\binom nnx^n$$.
Substitute $$x=i$$ to get$$(1+i)^n=\binom n0+\binom n1i-\binom n2-\binom n3i+\binom n4...$$
This gives$$\mathfrak R((1+i)^n)=\frac{S(n)}2\\\therefore S(n)=2\mathfrak R(2^{n/2}e^{in\pi/4})=2^{n/2+1}\cos(n\pi/4)$$