Sum of the series $\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{2}-\binom{n-3}{3}+..........$

Question

The sum of the series $$\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{2}-\binom{n-3}{3}+..........$$

$\bf{My\; Try::}$ We can write it as $\displaystyle \binom{n}{0} = $ Coefficient of $x^0$ in $(1+x)^n$

Similarly $\displaystyle \binom{n-1}{1} = $ Coefficient of $x^1$ in $(1+x)^{n-1}$

Similarly $\displaystyle \binom{n-2}{2} = $ Coefficient of $x^2$ in $(1+x)^{n-2}$

Now, how can I solve it after that, Help Required, Thanks

Answer 1

For any polynomial $f(x) = \sum\limits_{k=0}^{\deg f} a_k x^k$, we will use $[x^k] f(x)$ to denote $a_k$, the coefficient of $x^k$ in $f(x)$. Notice

$$\binom{n-k}{k} = [x^k](1+x)^{n-k} = [x^n] (x+x^2)^{n-k}$$

We have $$\require{cancel} \begin{align}\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k\binom{n-k}{k} &= \sum_{k=0}^n (-1)^k \binom{n-k}{k}\\ &= \sum_{k=0}^n [x^n] (x+x^2)^{n-k}(-1)^k = [x^n]\left(\sum_{k=0}^n (x+x^2)^{n-k}(-1)^k\right)\\ &= [x^n] \frac{(x+x^2)^{n+1}-(-1)^{n+1}}{1+x+x^2} = [x^n] \frac{[\color{red}{\cancel{\color{gray}{(x+x^2)^{n+1}}}} + (-1)^n](1-x)}{1-x^3}\\ &= (-1)^n [x^n] \frac{1-x}{1-x^3}\\ &= (-1)^n [x^n]\left((1 - x) + x^3(1-x) + x^6(1-x) + \cdots\right) \end{align} $$ Based on last expression, it is clear the sum depends only on $n \pmod 6$. Its value is given by following formula:

$$\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k\binom{n-k}{k} = \begin{cases} +1, & n \equiv 0, 1 \pmod 6\\ -1, & n \equiv 3, 4 \pmod 6\\ 0, & n \equiv 2, 5 \pmod 6 \end{cases}$$

Answer 2

Denote this sum by $S_n$ then from $${n+1 \choose m} = {n \choose m} + {n \choose m-1}$$ it follows that $$S_{n+1}=S_{n}-S_{n-1}.$$ Now start from $S_0= S_1= 1$ and you will notice the pattern.

Answer 3

Hint:

$$\binom{n}{0}= \mbox{ coefficient of } x^n \mbox{ in } (1+x)^n \\ \binom{n-1}{1}= \mbox{ coefficient of } x^n \mbox{ in } x^2(1+x)^{n-1} \\ \binom{n-2}{2}= \mbox{ coefficient of } x^n \mbox{ in } x^4(1+x)^{n-2} \\ ...$$

Hint 2: $$(1+x)^n-x^2(1+x)^{n-1}+x^4(1+x)^{n-2}-..=(1+x)^n \left(1-(\frac{x^2}{1+x})+ (\frac{x^2}{1+x})^2-(\frac{x^2}{1+x})^3 ...\right)$$

Answer 4

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

$\ds{{n \choose 0} - {n - 1 \choose 1} + {n - 2 \choose 2} - {n-3 \choose 3} + \cdots:\ ?}$.

\begin{align} \sum_{k = 0}^{n}\pars{-1}^{k}{n - k \choose k} & = \sum_{k = 0}^{\infty}\pars{-1}^{k}{n - k \choose n - 2k} = \sum_{k = 0}^{\infty}\pars{-1}^{k} \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n - k} \over z^{n - 2k + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n} \over z^{n + 1}} \sum_{k = 0}^{\infty}\pars{-\,{z^{2} \over 1 + z}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n} \over z^{n + 1}} {1 \over 1 + z^{2}/\pars{1 + z}}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{n + 1} \over z^{n + 1}\pars{z^{2} + z + 1}}\,{\dd z \over 2\pi\ic} \,\,\,\stackrel{z\ \mapsto\ 1/z}{=}\,\,\, \oint_{\verts{z}\ =\ 1^{\color{#f00}{+}}} {\pars{1 + z}^{n + 1} \over z^{2} + z + 1}\,{\dd z \over 2\pi\ic} \\[5mm] & = {\pars{1 + r}^{n + 1} \over 2r + 1} + {\pars{1 + \bar{r}}^{\, n + 1} \over 2\bar{r} + 1}\quad \mbox{where}\quad r \equiv -\,{1 \over 2} + {\root{3} \over 2}\,\ic = \exp\pars{{2\pi \over 3}\,\ic} \end{align}

---

Then $\ds{\pars{~\mbox{note that}\ 1 + r = \exp\pars{{\pi \over 3}\,\ic}~}}$, \begin{align} \sum_{k = 0}^{n}\pars{-1}^{k}{n - k \choose k} & = 2\,\Re\pars{\bracks{1 + r}^{n + 1} \over 2r + 1} = 2\,\Re\pars{\expo{\bracks{n + 1}\pi\ic/3} \over \root{3}\ic} \\[5mm] & = \bbox[10px,border:1px groove navy]{{2\root{3} \over 3} \,\sin\pars{\bracks{n + 1}\pi \over 3}} = \bbox[10px,border:1px groove navy]{% {\root{3} \over 3}\,\sin\pars{n\pi \over 3} + \cos\pars{n\pi \over 3}} \end{align}

This result generates the sequence $\ds{\pars{~\mbox{starting with}\ n = 0~}}$:

$$ \underbrace{1, 1, 0, -1, -1, 0}_{},\ \underbrace{1, 1, 0, -1, -1, 0}_{},\ \underbrace{1, 1, 0, -1, -1, 0}\ldots $$

because $\ds{\sin\pars{\bracks{n + 1}\pi \over 3} = \sin\pars{\bracks{n + \color{#f00}{6} + 1}\pi \over 3} = \sin\pars{\bracks{n + 7}\pi \over 3}}$.

Answer 5

Generating Functions $$ \begin{align} \sum_{n=0}^\infty\sum_{k=0}^n(-1)^k\binom{n-k}{k}x^n &=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^k\binom{n-k}{k}x^n\\ &=\sum_{k=0}^\infty\sum_{n=0}^\infty(-1)^k\binom{n}{k}x^{n+k}\\ &=\sum_{n=0}^\infty x^n(1-x)^n\\ &=\frac1{1-x(1-x)}\\ &=\frac1{1-x+x^2}\\ &=\frac{1+x}{1+x^3}\\[6pt] &=(1+x)(1-x^3+x^6-x^9+\dots)\\[11pt] &=1+x-x^3-x^4+x^6+x^7-x^9-x^{10}+\dots \end{align} $$ Therefore, $$ \sum_{k=0}^n(-1)^k\binom{n-k}{k}=\left\{\begin{array}{r} 1&\text{if }n\equiv0,1\pmod6\\ 0&\text{if }n\equiv2,5\pmod6\\ -1&\text{if }n\equiv3,4\pmod6 \end{array}\right. $$

Answer 6

Here is an answer based upon a transformation of generating series.

We show

\begin{align*} \sum_{j=0}^k\binom{k-j}{j}(-1)^j =\frac{(-1)^{\lfloor k/3\rfloor}+(-1)^{\lfloor (k+1)/3\rfloor}}{2} \qquad\qquad k\geq 0\tag{1} \end{align*}

where $\lfloor x \rfloor$ denotes the floor function. We set as upper limit of the sum $j=k$ and use $\binom{p}{q}=0$ if $q>p$. We will also use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series.

Note, the sum at the LHS of (1) is of the form \begin{align*} \sum_{j=0}^k\binom{k-j}{j}a_j \end{align*}

We can find in Riordan Array Proofs of Identities in Gould's Book by R. Sprugnoli in section 1.4 (A) a useful transformation formula:

Let $A(z)=\sum_{j=0}^\infty a_jz^j$ be a series, then the following holds \begin{align*} \frac{1}{1-z}A\left(\frac{z^2}{1-z}\right) =\sum_{k=0}^\infty\left(\sum_{j=0}^{k}\binom{k-j}{j}a_j\right)z^k \end{align*}

So, we have the following relationship \begin{align*} [z^k]A(z)=a_k\qquad\longleftrightarrow\qquad [z^k]\frac{1}{1-z}A\left(\frac{z^2}{1-z}\right)=\sum_{j=0}^{k}\binom{k-j}{j}a_j \tag{2}\end{align*}

We obtain from (1) with $a_j=(-1)^j$ the generating function $A(z)$ \begin{align*} A(z)=\sum_{j=0}^\infty(-z)^j=\frac{1}{1+z} \end{align*}

and conclude according to (2) \begin{align*} \sum_{j=0}^k\binom{k-j}{j}(-1)^j&=[z^k]\frac{1}{1-z}\cdot\frac{1}{1+\frac{z^2}{1-z}}\tag{3}\\ &=[z^k]\frac{1}{1-z+z^2}\tag{4}\\ &=[z^k]\left(1+z-z^3-z^4+z^6+z^7-z^9-z^{10}+\cdots\right)\tag{5}\\ &=\frac{(-1)^{\lfloor k/3\rfloor}+(-1)^{\lfloor (k+1)/3\rfloor}}{2}\tag{6} \end{align*} and the claim follows.

Comment:

• In (3) we apply the transformation formula (2).

• In (4) we do some simplifications.

• In (5) we expand the series with the help of Wolfram Alpha.

• In (6) we select the coefficient of $z^k$.

Note: This binomial identity can also be found as (1.75) in R. Sprugnoli's paper.

Answer 7

^{[Imported from a duplicate question]}

Chebyshev polynomials of the second kind have the following representation: $$ U_n(x)=\sum_{r\geq 0}\binom{n-r}{r}(-1)^r (2x)^{n-2r} \tag{1}$$ hence the wanted sum is just $U_n\left(\frac{1}{2}\right)$, and since $\frac{1}{2}=\cos\frac{\pi}{3}$, $$ U_n\left(\frac{1}{2}\right) = \frac{\sin((n+1)\pi/3)}{\sin(\pi/3)}.\tag{2} $$