Alternating sum of binomial coefficients identity

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.