4
$\begingroup$

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.

$\endgroup$

4 Answers 4

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D1X
    Commented Mar 20, 2017 at 11:28
  • $\begingroup$ @D1X It is a general definition of binomial coefficient. $$\binom{r}{k} = \frac{r(r-1)\cdots (r-k+1)}{k!}$$ $\endgroup$
    – PSPACEhard
    Commented Mar 20, 2017 at 11:36
  • $\begingroup$ Okay, thanks. Does $\sum_k$ represent $\sum_0^{\infty}$ in $(\clubsuit)$? $\endgroup$
    – D1X
    Commented Mar 20, 2017 at 12:18
  • $\begingroup$ @D1X Exactly... $\endgroup$
    – PSPACEhard
    Commented Mar 20, 2017 at 12:32
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Verified. (+1). $\endgroup$ Commented Mar 12, 2017 at 21:40
  • $\begingroup$ @MarkoRiedel: Many thanks, Marko! :-) $\endgroup$ Commented Mar 12, 2017 at 21:41
  • $\begingroup$ You might be interested in seeing this summation problem. $\endgroup$ Commented May 30, 2021 at 16:04
  • $\begingroup$ Respected Mr Scheuer, where did this formula $[z^i](1+z)^k=\binom{k}{i}$ come from? What is $[z^i]$? Explain, please. $\endgroup$ Commented May 28 at 14:20
  • $\begingroup$ @VadimChernetsov: An explanation is given in the first paragraph of my answer. See also the Definition at page 7 of H. S. Wilf's generatingfunctionology. $\endgroup$ Commented May 28 at 19:05
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .