# 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 !

-
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. –  Silynn Aug 5 '14 at 10:13

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.

-

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 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'll admit that this would not have been the way I would've tried to prove this :-) –  Henry Yuen 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. –  Felix Marin Jan 7 at 12:00