16
$\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$
  • $\begingroup$ This Question must have been asked here tons of times! Did you try to expand $(1-1)^n$? $\endgroup$ – kjetil b halvorsen Jun 18 '14 at 10:13
  • 7
    $\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$ – Jyrki Lahtonen 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
12
$\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$

$\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{#66f}{\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}}} \\[3mm]&=\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} =\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} \\[3mm]&=\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}} \\[3mm]&=\color{#66f}{\large\pars{-1}^{D}{n - 1 \choose D}} \end{align}

$\endgroup$
  • 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$ – Felix Marin Jan 7 '15 at 12:00
7
$\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$
  • $\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 at 15:17
  • $\begingroup$ Second above comment for more explanation $\endgroup$ – Nicholas Apr 17 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$
  • $\begingroup$ This is how a question asked in August '14 can be answered in June '14 :-) $\endgroup$ – Jyrki Lahtonen 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$
0
$\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$

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.