# Alternating sum of binomial coefficients identity

I need to show that the following identity holds:

$\sum_{i=0}^k (-1)^{k-i} {{d-i}\choose{k-i}} {{n}\choose{i}} = {{n-d+k-1}\choose{k}}$

Where $k \leq \frac{d}{2}$ and $n \geq d$.

I have been trying several substitutions but I haven't been able to prove it. Any help would be appreciated.

We have $$(-1)^{k-i} \binom{d-i}{k-i} = \binom{k - d - 1}{k-i} \tag{\spadesuit}$$ because for $0 \leq i < k$, \begin{align} (-1)^{k-i}\binom{d-i}{k-i} &= (-1)^{k-i}\frac{(d-i)(d-i-1)\cdots(d-k+1)}{(k-i)!} \\ &= \frac{(k - d - 1)(k - d - 2)\cdots (i-d)}{(k-i)!}\\ &= \binom{k-d-1}{k-i} \end{align} and for $i = k$, both LHS and RHS of $(\spadesuit)$ are $1$.

Therefore, we have \begin{align} \sum_{i=0}^k (-1)^{k-i}\binom{d-i}{k-i}\binom{n}{i} &= \sum_{i=0}^k\binom{k-d-1}{k-i}\binom{n}{i} \tag{$\clubsuit$} \end{align} By applying the famous identity $\sum_k \binom{r}{m+k}\binom{s}{n-k} = \binom{r+s}{m+n}$, $(\clubsuit)$ can be rewritten as $$\binom{n + k - d - 1}{k}$$

• I accepted this because it is the simplest one, but there seems to be a problem, k-d-1 can be a negative number. I am unsure of the definition used here for binomial coefficients with negative elements. – D1X Mar 20 '17 at 11:28
• @D1X It is a general definition of binomial coefficient. $$\binom{r}{k} = \frac{r(r-1)\cdots (r-k+1)}{k!}$$ – PSPACEhard Mar 20 '17 at 11:36
• Okay, thanks. Does $\sum_k$ represent $\sum_0^{\infty}$ in $(\clubsuit)$? – D1X Mar 20 '17 at 12:18
• @D1X Exactly... – PSPACEhard Mar 20 '17 at 12:32

It is convenient to use the coefficient of operator $[z^i]$ to denote the coefficient of $z^i$ in a series. This way we can write e.g. \begin{align*} [z^i](1+z)^k=\binom{k}{i} \end{align*}

We obtain \begin{align*} \sum_{i=0}^k&(-1)^{k-i}\binom{d-i}{k-i}\binom{n}{i}\\ &=\sum_{i=0}^\infty(-1)^{k-i}[z^{k-i}](1+z)^{d-i}[u^i](1+u)^n\tag{1}\\ &=(-1)^k[z^k](1+z)^d\sum_{i=0}^\infty(-1)^i\left(\frac{z}{1+z}\right)^i[u^i](1+u)^n\tag{2}\\ &=(-1)^k[z^k](1+z)^d\left(1-\frac{z}{1+z}\right)^n\tag{3}\\ &=(-1)^k[z^k](1+z)^{d-n}\tag{4}\\ &=(-1)^k\binom{d-n}{k}\tag{5}\\ &=\binom{n-d+k-1}{k} \end{align*} and the claim follows.

Comment:

• In (1) we apply the coefficient of operator twice and set the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator and use the rule \begin{align*} [z^{p-q}]A(z)=[z^p]z^qA(z) \end{align*}

• In (3) we apply the substitution rule of the coefficient of operator with $u:=-\frac{z}{1+z}$ \begin{align*} A(z)=\sum_{k=0}^\infty a_k z^k=\sum_{k=0}^\infty z^k [u^k]A(u) \end{align*}

• In (4) we select the coefficient of $z^k$.

• In (5) we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q \end{align*}

• Verified. (+1). – Marko Riedel Mar 12 '17 at 21:40
• @MarkoRiedel: Many thanks, Marko! :-) – Markus Scheuer Mar 12 '17 at 21:41


$\ds{\sum_{i = 0}^{k}\pars{-1}^{k - i}{d - i \choose k - i}{n \choose i} = {n - d + k - 1 \choose k}:\ {\large ?}. \qquad\qquad 0 \leq 2k \leq d \leq n}$.

\begin{align} \sum_{i = 0}^{k}\pars{-1}^{k - i}{d - i \choose k - i}{n \choose i} & = \sum_{i = 0}^{k}\pars{-1}^{k - i}\braces{% {-\bracks{d - i} + \bracks{k - i} - 1 \choose k - i}\pars{-1}^{k - i}} {n \choose i} \\[5mm] & = \sum_{i = 0}^{k}{k - d - 1 \choose k - i}{n \choose i} = \sum_{i = 0}^{k}{k - d - 1 \choose k - \bracks{k - i}}{n \choose k - i} \\[5mm] & = \sum_{i = 0}^{\color{#f00}{\infty}}{k - d - 1 \choose i}{n \choose k - i} \qquad\pars{~\mbox{because}\ \left.{n \choose k - i}\right\vert_{\ i\ >\ k\,,\ n\ \geq\ 0} = 0~} \\[5mm] & = \sum_{i = 0}^{\infty}{k - d - 1 \choose i} \bracks{z^{k - i}}\pars{1 + z}^{n} \\[5mm] & = \bracks{z^{k}}\bracks{\pars{1 + z}^{n} \sum_{i = 0}^{\infty}{k - d - 1 \choose i}z^{i}} \\[5mm] & = \bracks{z^{k}}\bracks{\pars{1 + z}^{n}\pars{1 + z}^{k - d - 1}} = \bracks{z^{k}}\pars{1 + z}^{n + k - d - 1} \\[5mm] & =\ \bbox[#ffe,15px,border:1px dotted navy]{\ds{n + k - d - 1 \choose k}} \end{align}