18
$\begingroup$

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 !

$\endgroup$
4
  • $\begingroup$ This Question must have been asked here tons of times! Did you try to expand $(1-1)^n$? $\endgroup$ Jun 18 '14 at 10:13
  • 8
    $\begingroup$ @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! $\endgroup$ Jun 18 '14 at 10:14
  • $\begingroup$ @JyrkiLahtonen: even if you did, the solution is not $0$ for $D <n$. $\endgroup$
    – Alex
    Jun 18 '14 at 12:24
  • $\begingroup$ 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. $\endgroup$
    – Silynn
    Aug 5 '14 at 10:13
14
$\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}$\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}

$\endgroup$
2
  • 3
    $\begingroup$ I'll admit that this would not have been the way I would've tried to prove this :-) $\endgroup$
    – Henry Yuen
    Aug 6 '14 at 11:53
  • $\begingroup$ @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. $\endgroup$ Jan 7 '15 at 12:00
13
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – UPS
    Apr 11 '19 at 15:17
  • $\begingroup$ Second above comment for more explanation $\endgroup$
    – Nicholas
    Apr 17 '19 at 3:35
7
$\begingroup$

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.

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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