# Identity involving binomial coefficients

I might have written this in a needlessly cumbersome way, but I want to prove that for odd positive integers $n$, $$\sum_{k\ odd}^{n}\binom{2n+1}{2k}=\begin{cases} \binom{2^n+1}{2}, & \text{if}\ n\ \text{mod}\ 4 =1\\ \binom{2^n}{2}, & \text{if}\ n\ \text{mod}\ 4 =3 \end{cases}$$ I have tested these identities and they should hold in general. Thank you very much in advance!

Edit: I found the following formula in the wikipedia article for binomial coefficients, under multisections of sums (https://en.wikipedia.org/wiki/Binomial_coefficient#Multisections_of_sums) which works nicely.$$\binom{n}{2}+\binom{n}{6}+\binom{n}{10}+\cdots=\frac{1}{2}(2^{n-1}-2^{\frac{n}{2}}\cos\frac{n\pi}{4})$$ It would be great if someone can provide a reference or proof for this. Or if there is a much faster way of getting at the same result then please ignore this entirely.

Hint: Use the binomial formula for $(1+1)^{2n+1}$, $(1-1)^{2n+1}$, $(1+i)^{2n+1}$ and $(1-i)^{2n+1}$:

$$A=(1+1)^{2n+1}=\binom{2n+1}{0}+\binom{2n+1}{1}+\binom{2n+1}{2}+\binom{2n+1}{3}+\cdots$$ $$B=(1-1)^{2n+1}=\binom{2n+1}{0}-\binom{2n+1}{1}+\binom{2n+1}{2}-\binom{2n+1}{3}+\cdots$$ $$C=(1+i)^{2n+1}=\binom{2n+1}{0}+\binom{2n+1}{1}i-\binom{2n+1}{2}-\binom{2n+1}{3}i+\cdots$$ $$D=(1-i)^{2n+1}=\binom{2n+1}{0}-\binom{2n+1}{1}i-\binom{2n+1}{2}+\binom{2n+1}{3}i+\cdots$$

so the requested sum is:

$$\binom{2n+1}{2}+\binom{2n+1}{6}+\cdots=\frac{1}{4}(A+B-C-D)$$

All it takes is to calculate $\frac{1}{4}(A+B-C-D)=\frac{1}{4}\left(2^{2n+1}-(1+i)^{2n+1}-(1-i)^{2n+1}\right)$. That can be done for the cases $n=4k+1$ and $n=4k+3$ separately.

For example, for $n=4k+1$, we have:

$$\frac{1}{4}\left(2^{2n+1}-(1+i)^{8k+3}-(1-i)^{8k+3}\right)=\frac{1}{4}\left(2^{2n+1}-2^{4k}\left((1+i)^3-(1-i)^3\right)\right)=\frac{1}{4}\left(2^{2n+1}+2^{4k+2}\right)=\frac{1}{2}(2^{2n}+2^n)=\binom{2^n+1}{2}$$

Above, we used the fact that $(1+i)^8=(1-i)^8=2^4$, and also $(1+i)^3+(1-i)^3=-4$.

The case $n=4k+3$ is similar.

• As a note: I think this is easier to see this with generating functions. If $f(x) = \sum_{n} a_n x^n$ then $\sum_{n \text{ even}} a_n x^n = \frac{f(x) + f(-x)}{2}$ (and summing over odd terms is similar). So you can start with $\sum \binom{2n + 1}{k} x^k = (1 + x)^{2n + 1}$, pass to the even terms, substitute $x^2 \mapsto x$ and then pass to odd terms. Feb 5, 2018 at 18:48

Preliminaries

Note that if $n\mid m$, then \begin{align} \frac1n\sum_{k=0}^{n-1}e^{2\pi ikm/n} &=\frac1n\sum_{k=0}^{n-1}1\\[6pt] &=1 \end{align} and that if $n\nmid m$, then \begin{align} \frac1n\sum_{k=0}^{n-1}e^{2\pi ikm/n} &=\frac1n\frac{e^{2\pi im}-1}{e^{2\pi im/n}-1}\\[6pt] &=0 \end{align} Thus, $$\frac1n\sum_{k=0}^{n-1}e^{2\pi ikm/n}=[\,n\mid m\,]$$ where $[\dots]$ are Iverson Brackets.

Therefore, setting $n=4$, we get \begin{align} [\,k\equiv0\pmod4\,] &=1^k+i^k+(-1)^k+(-i)^k\\ [\,k\equiv2\pmod4\,] &=1^{k-2}+i^{k-2}+(-1)^{k-2}+(-i)^{k-2}\\ &=1^k-i^k+(-1)^k-(-i)^k \end{align}

First Question \begin{align} \sum_{k=0}^n\frac{\overbrace{1^k-i^k+(-1)^k-(-i)^k}^{[\,k\equiv2\pmod4\,]}}4\binom{2n+1}{k} &=\frac{2^{2n+1}-(1+i)^{2n+1}+0^{2n+1}-(1-i)^{2n+1}}4\\ &=2^{2n-1}-2^{n-\frac12}\cos\left(\frac{(2n+1)\pi}4\right)\\[6pt] &=2^{2n-1}-2^{n-1}\left(\cos\left(\frac{n\pi}2\right)-\sin\left(\frac{n\pi}2\right)\right)\\[6pt] &=2^{2n-1}+2^{n-1}(-1)^{\left\lfloor\frac{n-1}2\right\rfloor}\\ &=\frac{2^n\left(2^n+(-1)^{\left\lfloor\frac{n-1}2\right\rfloor}\right)}2\\ &=\bbox[5px,border:2px solid #C0A000]{\left\{\begin{array}{} \binom{2^n+1}{2}&\text{if }n\equiv1,2\pmod4\\ \binom{2^n}{2}&\text{if }n\equiv0,3\pmod4 \end{array}\right.} \end{align}

Second Question \begin{align} \sum_{k=0}^n\frac{\overbrace{1^k-i^k+(-1)^k-(-i)^k}^{[\,k\equiv2\pmod4\,]}}4\binom{n}{k} &=\frac{2^n-(1+i)^n+0^n-(1-i)^n}4\\ &=\bbox[5px,border:2px solid #C0A000]{2^{n-2}-2^{\frac n2-1}\cos\left(\frac{n\pi}4\right)+\frac{[n=0]}4} \end{align}
