Truncated alternating binomial sum

Question

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 !

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

With @Aryabhata:'s idea:

Consider the binomial expansion $$(1+x)^{\alpha} = \sum_{k\ge 0} \binom{\alpha}{k} x^k$$ where $$\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}$$ and $0$ for integers $k<0$. Since $$(*) \ \ \ \ (1+x)^{\alpha}\cdot (1+x)^{\beta} = (1+x)^{\alpha+ \beta}$$ we get

$$(**) \ \ \ \sum_{l \ge 0} \binom{\alpha}{k-l} \binom{\beta}{l} = \binom{\alpha+ \beta}{k}$$

The above is true for any $\alpha$, $\beta$, and $k\ge 0$ an integer.

To get the desired formula, notice that $\binom{-1}{l} = (-1)^l$.

Notes:

1. The binomial coefficient $\binom{\alpha}{k}$ is can be defined for all $\alpha$ and $k$ ( complex). The formula $(**)$ is still valid for $k$ non-integer (but now summing infinitely many terms).

2. The binomial identity $(**)$ is equivalent to the equality $(*)$. It can be also proves as follows: consider it as an polynomial for variables $\alpha$, $\beta$. Since it is true for any pair $(\alpha, \beta) = (m,n)$, it is an identity.

3. We can modify the binomial coefficients to

$$\binom{\alpha}{k}_h\colon = \frac{\alpha(\alpha-h)\cdots(\alpha - (k-1) h)}{k!}$$

Now the equality

$$\binom{\alpha+ \beta}{r}_h = \sum_{p+q=r} \binom{\alpha}{p}_h \cdot \binom{\beta}{q}_h$$ as $h\to 0$ becomes the binomial formula for $(\alpha+\beta)^r$.