9
$\begingroup$

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?

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

6 Answers 6

6
$\begingroup$

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

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

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.

$\endgroup$
8
  • $\begingroup$ Thanks. I know about generating function. May I derive from it that $a_{2n+1}+a_{2n+3}+a_{2n+5}=0.$? $\endgroup$
    – Leox
    Sep 18, 2014 at 20:12
  • $\begingroup$ @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$. $\endgroup$ Sep 18, 2014 at 20:23
  • $\begingroup$ 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? $\endgroup$
    – Leox
    Sep 18, 2014 at 20:34
  • $\begingroup$ @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. $\endgroup$ Sep 18, 2014 at 20:52
  • $\begingroup$ @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. $\endgroup$ Sep 18, 2014 at 20:54
2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks both @MarkoRiedel and the OP. $\endgroup$ Sep 20, 2014 at 19:02
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .