Identity involving binomial coefficients

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k\ odd}^{n}{2n + 1 \choose 2k} & = \sum_{k = 0}^{\infty}{2n + 1 \choose 2\bracks{2k + 1}} = \sum_{k = 1}^{\infty}{2n + 1 \choose 2k}\,{1 - \pars{-1}^{k} \over 2} = {1 \over 2}\sum_{k = 1}^{\infty}{2n + 1 \choose 2k}\pars{1 - \ic^{2k}} \\[5mm] & = {1 \over 2}\sum_{k = 2}^{\infty}{2n + 1 \choose k} \pars{1 - \ic^{k}}{1 + \pars{-1}^{k} \over 2} \\[5mm] & = {1 \over 4}\sum_{k = 2}^{\infty}{2n + 1 \choose k} + {1 \over 4}\sum_{k = 2}^{\infty}{2n + 1 \choose k}\pars{-1}^{k} \\[2mm] & \underbrace{-{1 \over 4}\sum_{k = 2}^{\infty}{2n + 1 \choose k}\ic^{k} - {1 \over 4}\sum_{k = 2}^{\infty}{2n + 1 \choose k}\pars{-\ic}^{k}} _{\ds{-\,{1 \over 2}\,\Re\sum_{k = 2}^{\infty}{2n + 1 \choose k}\ic^{k}}} \\[5mm] & = {1 \over 4}\bracks{\pars{1 + 1}^{2n + 1} - 1 - \pars{2n + 1}} + {1 \over 4}\bracks{\pars{1 - 1}^{2n + 1} - 1 + \pars{2n + 1}} \\[2mm] & -{1 \over 2}\,\Re\bracks{\pars{1 - \ic}^{2n + 1} - 1 - \pars{2n + 1}\ic} \\[5mm] & = 2^{2n - 1} - {1 \over 2} - {1 \over 2}\,\Re\bracks{\root{2}\expo{-\pi\ic/4}}^{2n + 1} + {1 \over 2} = 2^{2n - 1} - {1 \over 2}\,\Re\bracks{2^{n + 1/2}\expo{-\pars{2n + 1}\pi\ic/4}} \\[5mm] & = 2^{2n - 1} - 2^{n - 1/2}\cos\pars{\bracks{2n + 1}\pi \over 4} \\[5mm] & = 2^{2n - 1} - 2^{n - 1/2}\bracks{\cos\pars{n\pi \over 2}\cos\pars{\pi \over 4} - \sin\pars{n\pi \over 2}\sin\pars{\pi \over 4}} \\[5mm] & = 2^{2n - 1}\bracks{1 - \cos\pars{n\pi \over 2} + \sin\pars{n\pi \over 2}} \\[5mm] & = \bbx{\left\{\begin{array}{lcl} \ds{2^{2n - 1}\bracks{1 - \pars{-1}^{n/2}}} & \mbox{if} & \ds{n}\ \mbox{is}\ even \\[2mm] \ds{2^{2n - 1}\bracks{1 + \pars{-1}^{\pars{n - 1}/2}}} & \mbox{if} & \ds{n}\ \mbox{is}\ odd \end{array}\right.} \end{align}