# Truncated alternating binomial sum

It is easily checked that $\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem.

I'm trying to figure out what happens with the truncated sum $\displaystyle\sum_{i\ =\ 0}^{D}\left(\, -1\,\right)^{i}\binom{n}{i}$.
How far away from $0$ can this get, as a function of $D$ ?.

I'm mostly interested in the case of when $D \ll n$, such as $D \sim \,\sqrt{\,n\,}\,$.

Thanks !

• This Question must have been asked here tons of times! Did you try to expand $(1-1)^n$? Jun 18 '14 at 10:13
• @kjetil: Did you notice that the summation doesn't go up to $n$? Or have I missed this version tons of times? Not ruling out the possibility! Jun 18 '14 at 10:14
• @JyrkiLahtonen: even if you did, the solution is not $0$ for $D <n$.
– Alex
Jun 18 '14 at 12:24
• I'm still working on the proof myself, but look at $D=n-2$ and then use induction from there, the result is surprisingly simple. Aug 5 '14 at 10:13

$$\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}$$\begin{align} &\color{#88f}{\large\sum_{k = 0}^{D}\pars{-1}^{k}{n \choose k}} =\sum_{k = 0}^{D}\pars{-1}^{k}\ \overbrace{\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1} {\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ {n \choose k}}} \\[5mm]& \ =\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{D}\pars{-\,{1 \over z}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}{\pars{1 + z}^{n} \over z} {\pars{-1/z}^{D} + z \over 1 + z}\,{\dd z \over 2\pi\ic} \\[5mm]&=\pars{-1}^{D}\ \underbrace{\oint_{\verts{z}\ =\ a\ <\ 1} {\pars{1 + z}^{n - 1} \over z^{D + 1}}\,{\dd z \over 2\pi\ic}} _{\ds{=\ {n - 1 \choose D}}}\ +\ \underbrace{\oint_{0\ <\ \verts{z}\ =\ a\ <\ 1}\pars{1 + z}^{n - 1} \,{\dd z \over 2\pi\ic}}_{\ds{=\ 0}} \\[5mm]&\ = \bbox[10px,border:1px groove navy]{\pars{-1}^{D}{n - 1 \choose D}} \\ & \end{align}

• I'll admit that this would not have been the way I would've tried to prove this :-) Aug 6 '14 at 11:53
• @HenryYuen However, we'll go straightforward to the end. It's quite useful in more complicated cases. You can check my answers and there you'll find a lot of applications of this method. Thanks. Jan 7 '15 at 12:00

Let $n\ge 2\in\mathbb N$ (since the case $n=1$ is trivial).

For $0\le D\lt n$, we can prove the following by induction: $$\sum_{i=0}^{D}(-1)^i\binom{n}{i}=(-1)^D\binom{n-1}{D}.$$

For $D=0$, it holds trivially.

For a $D$ such that $0\le D\le n-2$, suppose that it holds. Then, \begin{align}\sum_{i=0}^{D+1}(-1)^i\binom{n}{i}&=(-1)^{D+1}\binom{n}{D+1}+\sum_{i=0}^{D}(-1)^i\binom{n}{i}\\&=(-1)^{D+1}\binom{n}{D+1}+(-1)^D\binom{n-1}{D}\\&=(-1)^{D+1}\left\{\binom{n}{D+1}-\binom{n-1}{D}\right\}\\&=(-1)^{D+1}\binom{n-1}{D+1}\end{align} Hence, it holds when $D+1$.

Therefore, it holds for any $0\le D\lt n$. Q.E.D.

From this, you'll also see how far away from $0$ it can get.

Use the following:

$$(1-x)^{n-1} = (1-x)^n \times \frac{1}{1-x} = (1-x)^n (1 + x + x^2 + \dots) =$$ $$\left(1 + n(-x) + \binom{n}{2}(-x)^2 + \dots + (-x)^n\right)(1+x+x^2 + \dots)$$

Now, mutiplying any polynomial (or power series) by $1 + x + x^2 + \dots$ has the effect of giving you the truncated sums of the coefficients of the polynomial as the coefficients of the powers of $x$ in the resulting power series.

In your case, the resulting series is itself a polynomial, $(1-x)^{n-1}$, giving you a neat closed form answer.

• I don't understand how you get the end result. Could you please elaborate? Is the idea that, $\sum_{i=0}^D (-1)^i {n\choose i}$ is exactly the D-th derivative of $(1-x)^{n-1}$ evaluated at $x=0$?
– UPS
Apr 11 '19 at 15:17
• Second above comment for more explanation Apr 17 '19 at 3:35

Hint: The answer will be $(-1)^D{n-1\choose D}$. The proof goes by induction on $D$, and uses the Pascal triangle rule.

This answer was moved here from an older question due to a merger. In that question the parameter $D$ was called $k$. I edited this answer to match with that.

• This is how a question asked in August '14 can be answered in June '14 :-) Apr 11 '17 at 6:07

First, let us write $$\sum_{i=0}^{D} (-1)^i \binom{n}{i}=\sum_{i=0}^D \binom{i-n-1}{i}$$ This step can be proven by using the definition of binomial coefficient and pulling a $-1$ out of each term.

Next, $$\sum_{i=0}^D \binom{i-n-1}{i}=\binom{D-n}{D}$$ can be proven inductively.

And finally, this can be simplified using the same result in the first step. $$\binom{D-n}{D}=(-1)^D\binom{n-1}{D}$$

Use the remainder term of a truncated Taylor series: $$(1+x)^n=\sum_{k=0}^n{n \choose k}x^k=\sum_{k=0}^r{n \choose k}x^k + \int_0^x \frac{f^{(r+1)}(t)}{r!}(x-t)^r\,dt$$ Rearrange to put the truncated series on the LHS: \begin{align} \sum_{k=0}^r{n \choose k}x^k &= (1+x)^n - \int_0^x \frac{f^{(r+1)}(t)}{r!}(x-t)^r\,dt \\&= (1+x)^n - \frac{1}{r!}\frac{n!}{(n-r-1)!} \int_0^x (1+t)^{n-r-1}(x-t)^r\,dt \end{align} Substitute $$x=-1$$: \begin{align} \sum_{k=0}^r{n \choose k}(-1)^k &= 0-\frac{1}{r!}\frac{n!}{(n-r-1)!} (-1)^{r}\int_0^{-1} (1+t)^{n-1}\,dt\\ &=\frac{(-1)^{r+1}}{r!}\frac{(n-1)!}{(n-r-1)!}[(1+t)^n]_0^{-1} \\&=\frac{(-1)^{r}}{r!}\frac{(n-1)!}{(n-r-1)!} \\&=(-1)^r{n-1\choose r} \end{align}

# Bijective proof

In this answer, I'm assuming the identity is already known, but a bijective proof is sought.

Rearrange $$\sum_{i=0}^{D}(-1)^i\binom{n}{i}=(-1)^D\binom{n-1}{D}$$ to get the equivalent statement $$\sum_{i=0}^{D}\binom{n}{i}[i\text{ even}] + [D\text{ odd}]\binom{n-1}{D} = \sum_{i=0}^{D}\binom{n}{i}[i\text{ odd}] + [D\text{ even}]\binom{n-1}{D}$$ where I'm using Iverson Bracket notation.

Let $$2^{[n]}$$ denote the set of strings of length $$n$$ made up of $$0$$s and $$1$$s. Consider a transformation $$\mathtt{FLIPFIRST}:2^{[n]} \to 2^{[n]}$$ that flips the first digit. A bijective proof of the above claim can be found using $$\mathtt{FLIPFIRST}$$.

Observe that $$\mathtt{FLIPFIRST}$$ is injective, because $$\mathtt{FLIPFIRST}(\mathtt{FLIPFIRST}(s))=s$$. $$\mathtt{FLIPFIRST}$$ maps a string with an odd number of $$1$$ to one with an even number of $$1$$s, and vice versa. If a string has $$D$$ $$1$$s, then its output may have $$D+1$$ or $$D-1$$ $$1$$s. The number of strings $$s$$ such that $$\mathtt{FLIPFIRST}(s)$$ has $$D+1$$ $$1$$s is $$\binom{n-1}{D}$$.

Let us write $$S_{n,m}=\sum_{k=o}^{m} (-1)^k~ {n \choose k},$$ then $$S_{n,m}={n \choose 0}-{n \choose 1}+{n\choose 2}-{n\choose 3}+......+ (-1)^m {n \choose m}.$$ $$\Rightarrow S_{n,m}= [x^0]~ \left ((1-x)^n+(1-x)^n \frac{1}{x}+(1-x)^n \frac{1}{x^2}+(1-x)^n\frac{1}{x^3}+....+(1-x)^n \frac{1}{x^m}\right).$$ $$[x^j]~$$ is short for `coefficient of $$x^j$$ in '. We can write $$S_{n,m}=[x^0] ~ (1-x)^n \left(1+\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}+...+\frac{1}{x^m}\right).$$ $$\Rightarrow S_{n,m}=[x^0]~(1-x)^n \frac{1}{x^m} \left(\frac{1-x^{m+1}}{1-x} \right)= [x^m]~[ (1-x)^{n-1}-(1-x)^{n-1} x^{m+1}].$$ $$\Rightarrow S_{n,m}= (-1)^m {n-1 \choose m}$$

Just to show another way \eqalign{ & \sum\limits_{i = 0}^D {\left( { - 1} \right)^{\,i} \left( \matrix{ n \cr i \cr} \right)} = \sum\limits_{i = 0}^D {\left( \matrix{ i - n - 1 \cr i \cr} \right)} = \cr & = \sum\limits_i {\left( \matrix{ D - i \cr D - i \cr} \right) \left( \matrix{ i - n - 1 \cr i \cr} \right)} = \cr & = \left( { - 1} \right)^{\,D} \sum\limits_i {\left( \matrix{ - 1 \cr D - i \cr} \right) \left( \matrix{ n \cr i \cr} \right)} = \cr & = \left( { - 1} \right)^{\,D} \left( \matrix{ n - 1 \cr D \cr} \right) \quad \left| \matrix{ \;n \in \mathbb C \hfill \cr \;0 \le D \in \mathbb Z \hfill \cr} \right. \cr} where the steps are:

• upper negation;
• replacing the bounds on the sum with a binomial;
• upper negation on both binomials;
• Vandermonde convolution.