# Calculate the binomial sum $I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}$

I need any hint with calculating of the sum $$I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i}.$$ Maple give the strange unsimplified result
$$I_n={\frac {1/12\,i\sqrt {3} \left( - \left( \left( 1+i\sqrt {3} \right) ^{2\,{\it n}+2} \right) ^{2}+16\, \left( -1 \right) ^{2\,{\it n}} \left( {2}^{2\,{\it n}} \right) ^{2} \right) }{{2}^{2\,{\it n}} \left( 1+i\sqrt {3} \right) ^{2\,{\it n}+2}}},$$ Сalculation for small $n$ are as follows $I_1=-1, I_2=0,I_3=1, I_4=-1, \ldots$ and leads to a hypothese: $I_n= -1 \text{ for } n=3k+1, =0, \text{ for } n=3k+2,=1, \text{ for } n=3k.$ But how to prove it?

• The Maple result is equivalent to the first form I give in $(5)$ in my answer.
– robjohn
Sep 19, 2014 at 11:58
• This seems related to (and has answers similar to) this question. I even wrote an answer that I forgot about.
– robjohn
Sep 19, 2014 at 17:47

Generating Functions

Let's compute the generating function of $\displaystyle\sum_{k=0}^n(-1)^k\binom{n-k}{k}$: \begin{align} \sum_{n=0}^\infty\sum_{k=0}^n(-1)^k\binom{n-k}{k}x^n &=\sum_{k=0}^\infty(-1)^kx^k\sum_{n=k}^\infty\binom{n-k}{k}x^{n-k}\\ &=\sum_{k=0}^\infty(-1)^kx^k\frac{x^k}{(1-x)^{k+1}}\\ &=\frac1{1-x}\frac1{1+\frac{x^2}{1-x}}\\ &=\frac1{1-x+x^2}\tag{1} \end{align} What the question asks is for the odd terms, which we get by taking the odd part of $(1)$: $$\frac12\left(\frac1{1-x+x^2}-\frac1{1+x+x^2}\right)=\frac{x}{1+x^2+x^4}\tag{2}$$ which implies that $\displaystyle\sum_{k=0}^n(-1)^k\binom{2n+1-k}{k}$ satisfies the recurrence $$a_n=-a_{n-1}-a_{n-2}\tag{3}$$ and starts out: $(1,-1,0,1,-1,\dots)$ and $(3)$ ensures that it will follow this pattern. That is, $$\boxed{\displaystyle\bbox[5px]{ \sum_{k=0}^n(-1)^k\binom{2n+1-k}{k}=\left\{\begin{array}{rl} 1&\text{if }n\equiv0\pmod{3}\\ -1&\text{if }n\equiv1\pmod{3}\\ 0&\text{if }n\equiv2\pmod{3}\\ \end{array}\right.}}\tag{4}$$

Solving the Recurrence $\boldsymbol{(3)}$

We can also get a solution by solving the recurrence $(3)$.

Since the roots of $x^2+x+1$ are $\frac{-1\pm i\sqrt3}{2}=e^{\pm i2\pi/3}$ and $a_0=1$ and $a_1=-1$, we get the general solution to be \begin{align} a_n &=\frac{\left(\frac{-1+i\sqrt3}2\right)^{n+1}-\left(\frac{-1-i\sqrt3}2\right)^{n+1}}{i\sqrt3}\\[6pt] &=\frac{e^{i2\pi(n+1)/3}-e^{-i2\pi(n+1)/3}}{i\sqrt3}\\[4pt] &=\frac2{\sqrt3}\sin\left(\frac{2\pi(n+1)}{3}\right)\tag{5} \end{align}

• (+1) Good work. The detour via complex variables appears not to be necessary here. Sep 18, 2014 at 23:49

This is much easier if we instead compute the sequence $a_m := \sum_{i=0}^\infty y^i {{m-i} \choose i}$ (note that most terms are zero). Then it is immediate that $a_{m+2}= a_{m+1}+y a_m$, from comparing terms and using $[y^{i-1}]a_m + [y^i] a_{m+1} = {{m-(i-1)}\choose{i-1}}+{{m+1-i}\choose{i}} = {{m+2-i}\choose{i}} = [y^i]a_{m+2}$.

Substituting $y=-1$, it is not hard to see that the sequence $a_m$ has period $6$ (for example, the characteristic polynomial is cyclotomic). So $a_{2n+1}$ has period $3$.

This approach was inspired by looking at generating functions, which are a very powerful tool when you don't know what's going on. I've included that approach below.

Side note: the case $y=-1/4$ is particularly interesting, as we get the very clean answer of $a_m = (m+1)2^{-m}$.

Alternate solution, using generating functions:

$$f(x) := \sum_m a_m x^m$$

$$= \sum_i y^i \sum_{m\geq 2i} {{m-i}\choose i} x^m = \sum_i (xy)^i \sum_{m'\geq i} {m'\choose i} x^{m'}$$

$$= \sum_i (x y)^i \frac{x^i}{(1-x)^{i+1}} = \frac{1}{1-x} \sum_i \left(\frac{x^2y}{1-x} \right)^i$$

$$= \frac{1}{1-x} \frac{1}{1-\frac{x^2 y}{1-x}} = \frac{1}{1-x-x^2 y}$$

Finally, we can read off the coefficients of $f(x)$ using partial fractions.

• Thanks. I know about generating function. May I derive from it that $a_{2n+1}+a_{2n+3}+a_{2n+5}=0.$?
– Leox
Sep 18, 2014 at 20:12
• @Leox In the case $y=-1$, yes, it is fairly straightforward: we have, immediately, that $a_n - a_{n+1}+a_{n+2}=0$ (just multiply out by $1-x+x^2$). Adding this for $n$, $n+1$, and $n+2$ gives us $a_n + a_{n+2}+a_{n+4}=0$. Sep 18, 2014 at 20:23
• Please clarify what is the upper bound in the sum in the expression for $a_m$? Or such reccurence relation does not depend on any upper bound?
– Leox
Sep 18, 2014 at 20:34
• @Leox The upper bound is always $+\infty$, but there are some minor concerns regarding some conventions I'm using implicitly. I've added a couple of bounds to deal with possible confusion. Sep 18, 2014 at 20:52
• @Leox Also, in case it wasn't clear: there are two solutions here, one with generating functions and one without. I didn't write out all the details of the first solution, but it's very straightforward, if you wanted to use direct manipulation rather than generating functions. Sep 18, 2014 at 20:54

Start by restating the problem: we seek to evaluate $$\sum_{q=0}^n (-1)^q {2n+1-q\choose q} = \sum_{q=0}^n (-1)^q {2n+1-q\choose 2n+1-2q}.$$

Introduce the integral representation $${2n+1-q\choose 2n+1-2q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1-q}}{z^{2n+2-2q}} \; dz.$$

This gives the following for the sum (note that the integral correctly represents the fact of the binomial coefficient being zero for $q>n$, so we may extend the sum to infinity): $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2n+2}} \sum_{q\ge 0} (-1)^q \frac{z^{2q}}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{2n+2}} \frac{1}{1+z^2/(1+z)} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+2}}{z^{2n+2}} \frac{1}{1+z+z^2} \; dz.$$

Extracting coefficients we find $$\sum_{q=0}^{2n+1} {2n+2\choose 2n+1-q} [z^q] \frac{1}{1+z+z^2} = \sum_{q=0}^{2n+1} {2n+2\choose q+1} [z^q] \frac{1}{1+z+z^2}.$$

Introduce the generating function $$Q(w) = \sum_{n\ge 0} w^{2n+1} \sum_{q=0}^{2n+1} {2n+2\choose q+1} [z^q] \frac{1}{1+z+z^2},$$ which is $$\sum_{q\ge 0} w^q [z^q] \frac{1}{1+z+z^2} \sum_{2n+1\ge q} {2n+2\choose q+1} w^{2n+1-q} \\ = \sum_{q\ge 0} w^q [z^q] \frac{1}{1+z+z^2} \sum_{p\ge 0} {p+q+1\choose q+1} w^p \\ = \sum_{q\ge 0} w^q [z^q] \frac{1}{1+z+z^2} \frac{1}{(1-w)^{q+2}} \\ = \frac{1}{(1-w)^2} \sum_{q\ge 0} \left(\frac{w}{1-w}\right)^q [z^q] \frac{1}{1+z+z^2}.$$

What we have here is an annihilated coefficient extractor and the sum simplifies to $$Q(w) = \frac{1}{(1-w)^2} \frac{1}{1+w/(1-w) + w^2/(1-w)^2} \\ = \frac{1}{(1-w)^2+w(1-w) + w^2} = \frac{1}{1-w+w^2}.$$

This is the ordinary generating function of a sequence with recurrence $$a_{n+2} = a_{n+1} - a_n.$$ Since $a_0 = 1$ and $a_1 = 1$ we obtain $$1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0\ldots$$ thereby proving periodicity with period six.

Selecting the odd-index values preserves periodicity and we get the sequence $$1, -1, 0, 1, -1, 0, \ldots$$

Post Scriptum. If we introduce $$\rho_{1,2} = \frac{1\pm i\sqrt{3}}{2} \quad\text{and set}\quad c_{1,2} = \frac{3\pm i\sqrt{3}}{6}$$ we have the closed form $$[w^n] \frac{1}{1-w+w^2} = c_1 \rho_1^{-n} + c_2 \rho_2^{-n}$$ from which $[w^{2n+1}] Q(w)$ may be extracted.

The technique of annihilated coefficient extractors (ACE) is also employed at this MSE link I and this MSE link II.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{I_{n}\equiv\sum_{k = 0}^{n}\pars{-1}^{k}{ 2n + 1 - k \choose k}:\ {\large ?}}$

Since $\quad\ds{{ 2n + 1 - k \choose k} = 0}\quad$ when $\quad\ds{k > 2n + 1 - k\ \imp\ k> n + \half\ \imp\ k \geq n + 1}\quad$ it's true that $$\sum_{k = 0}^{n}\pars{-1}^{k}{ 2n + 1 - k \choose k} =\sum_{k = 0}^{\color{#c00000}{\Large\infty}}\pars{-1}^{k}{ 2n + 1 - k \choose k}$$

With $\ds{a > 1}$: \begin{align} I_{n}&=\sum_{k = 0}^{\infty}\pars{-1}^{k} \oint_{\verts{z}\ =\ a} {\pars{1 + z}^{2n + 1 - k} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{2n + 1} \over z}\sum_{k = 0}^{\infty} \bracks{-\,{1 \over z\pars{1 + z}}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a}{\pars{1 + z}^{2n + 1} \over z} {1 \over 1 + 1/\bracks{z\pars{1 + z}}}\,{\dd z \over 2\pi\ic} =\oint_{}{\pars{1 + z}^{2n + 2} \over z^{2} + z + 1}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a} {\pars{1 + z}^{2n + 2} \over \pars{z - r}\pars{z - r^{*}}} \,{\dd z \over 2\pi\ic}\qquad\mbox{where}\quad r \equiv \exp\pars{2\pi\ic \over 3} = -\,\half + {\root{3} \over 2}\,\ic \end{align}

Then, \begin{align} I_{n}&={\pars{1 + r}^{2n + 2} \over r - r^{*}} +{\pars{1 + r^{*}}^{2n + 2} \over r^{*} - r} =2\,\Re\bracks{\pars{1 + r}^{2n + 2} \over r - r^{*}} =2\,\Re\bracks{\pars{1 + r}^{2n + 2} \over 2\ic\,\Im r} \\[5mm]&={1 \over \Im r}\,\Im\pars{1 + r}^{2n + 2} ={2\root{3} \over 3}\,\Im\pars{\half + {\root{3} \over 2}\,\ic}^{2n + 2} ={2\root{3} \over 3}\,\Im\bracks{\exp\pars{\pi\ic \over 3}}^{2n + 2} \\[5mm]&={2\root{3} \over 3}\,\Im\exp\pars{\pars{2n + 2}\pi\ic \over 3} \end{align}

$$\color{#66f}{\large I_{n}\equiv\color{#66f}{\large\sum_{k = 0}^{n}\pars{-1}^{k}{ 2n + 1 - k \choose k}} =\color{#66f}{\large{2\root{3} \over 3}\,\sin\pars{\bracks{2n + 2}\pi \over 3}}}$$

• Thanks both @MarkoRiedel and the OP. Sep 20, 2014 at 19:02

Since $\dbinom{n}{r} = 0$ for $r > n$, we can rewrite the sum as

$$\text{S} = \sum_{r=0}^{\infty} (-1)^r \dbinom{2n+1-r}{r}$$

From the Binomial Theorem, we see that the sum is the coefficient of $x^n$ in

$$f(x) = x^n (1-x)^{2n+1} + x^{n-1} (1-x)^{2n} + \ldots$$

$$= \dfrac{(1-x)^{n+1}}{x^2-x+1}$$

Note that,

$$\sum_{n=0}^{\infty}{{U}_{r}(a) {x}^{r}} = \dfrac{1}{x^2 -2ax+1}$$

where $U_{r} (x)$ is the Chebyshev Polynomial of the second kind.

Putting $a = \dfrac{1}{2}$, we see that,

$$f(x) = (1-x)^{n+1} \sum_{n=0}^{\infty}{{U}_{r} \left( \dfrac{1}{2} \right) {x}^{r}} \quad (*)$$

To calculate the coefficient of $x^n$ in $(*)$, we see that coefficient of $x^{n-r}$ for fixed $r$ in $(1-x)^{n+1}$ is $(-1)^{n-r} \dbinom{n+1}{n-r}$, so coefficient of $x^n$ is,

$$\sum_{r=0}^{n} (-1)^{n-r} \dbinom{n+1}{n-r} U_{r} \left(\dfrac{1}{2}\right)$$

Substituting $r \mapsto r-1$, we have,

$$\text{S} = \sum_{r=1}^{n+1} (-1)^{n+1-r} \dbinom{n+1}{n+1-r} U_{r-1} \left(\dfrac{1}{2}\right)$$

$$= (-1)^{n+1} \sum_{r=1}^{n+1} (-1)^{r} \dbinom{n+1}{r} U_{r-1} \left(\dfrac{1}{2}\right) \quad \quad \left( \because \dbinom{n}{n-r} = \dbinom{n}{r} \right)$$

$$= (-1)^{n+1} \left( \dfrac{2}{\sqrt{3}} \right) \sum_{r=1}^{n+1} (-1)^{r} \dbinom{n+1}{r} \sin \left( \dfrac{r \pi}{3} \right) \quad \quad \left( \because U_{r-1} \left(\dfrac{1}{2}\right) = \sin \left( \dfrac{r \pi}{3} \right) \right)$$

$$(-1)^{n+1} \left( \dfrac{2}{\sqrt{3}} \right) \sum_{r=0}^{n+1} (-1)^{r} \dbinom{n+1}{r} \sin \left( \dfrac{r \pi}{3} \right) \quad \quad \left( \because \sin 0 = 0 \right)$$

Now, $$\displaystyle \sum_{r=0}^{n+1} (-1)^{r} \dbinom{n+1}{r} \sin \left( \dfrac{r \pi}{3} \right) = \Im \left( \sum_{r=0}^{n+1} (-1)^{r} \dbinom{n+1}{r} e^{\frac{i r \pi}{3}} \right) = (-1)^{n+1} \sin \left( \dfrac{2 (n+1) \pi}{3} \right)$$

$$\implies \text{S} = \dfrac{2}{\sqrt{3}} \sin \left( \dfrac{2 (n+1) \pi}{3} \right) \quad \square$$

Using Maple I am obtaining

$$\left( 1/6\,i\sqrt {3}+1/2 \right) \left( -1/2+1/2\,i\sqrt {3} \right) ^{n}+ \left( 1/2-1/6\,i\sqrt {3} \right) \left( -1/2-1/2\,i \sqrt {3} \right) ^{n}$$

and it is rewritten as

$$1/6\, \left( i\sqrt {3}+3 \right) \left( -1 \right) ^{n}{e}^{-1/3\,i \pi \,n}-1/6\, \left( -3+i\sqrt {3} \right) \left( -1 \right) ^{n}{e} ^{1/3\,i\pi \,n}$$

Then your conjecture is correct. It is verified using Maple.

• the Maple verifiation is not a proof.
– Leox
Sep 18, 2014 at 19:11
• Maple is generating the correct analytical result for the sum. It is a proof assisted by computer. Do you agree? Sep 18, 2014 at 19:26
• I belive that the Maple calculation is correct. But I need math proof by hand.
– Leox
Sep 18, 2014 at 19:34