2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marcus M Feb 5 '18 at 18:48
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.