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.
 A: 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}
$$
A: 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*}
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\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}
A: Here is another variation which is quite compact.
We seek
$$\sum_{q=0}^k (-1)^{k-q} {d-q\choose k-q} {n\choose q}
= \sum_{q=0}^k (-1)^{k-q} {d-q\choose d-k} {n\choose q}.$$
This is
$$(-1)^k \sum_{q=0}^k {n\choose q} (-1)^q
[z^{k-q}] \frac{1}{(1-z)^{d-k+1}}
\\ = (-1)^k [z^k] \frac{1}{(1-z)^{d-k+1}}
\sum_{q=0}^k {n\choose q} (-1)^q z^q.$$
Here the coefficient extractor enforces the range of the sum
and we get
$$(-1)^k [z^k] \frac{1}{(1-z)^{d-k+1}}
\sum_{q\ge 0} {n\choose q} (-1)^q z^q
\\ = (-1)^k [z^k] (1-z)^{n-d+k-1}
= {n-d+k-1\choose k}.$$
We have taken the condtions on $k,d$ and $n$ into account.
