2
$\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$
1
$\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$
  • $\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 Mar 20 '17 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 Mar 20 '17 at 11:36
  • $\begingroup$ Okay, thanks. Does $\sum_k$ represent $\sum_0^{\infty}$ in $(\clubsuit)$? $\endgroup$ – D1X Mar 20 '17 at 12:18
  • $\begingroup$ @D1X Exactly... $\endgroup$ – PSPACEhard Mar 20 '17 at 12:32
1
$\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$
  • $\begingroup$ Verified. (+1). $\endgroup$ – Marko Riedel Mar 12 '17 at 21:40
  • $\begingroup$ @MarkoRiedel: Many thanks, Marko! :-) $\endgroup$ – Markus Scheuer Mar 12 '17 at 21:41
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.