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 !

Solution 1:

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

Solution 2:

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.

Solution 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.

Solution 4:

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.