Combinatorial sum identity for a choose function $\sum\limits_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ [duplicate]

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

\begin{equation} \sum_{k = -m}^{n}{m + k \choose r}{n - k \choose s} = {m + n + 1 \choose r + s + 1}:\ {\large ?} \label{1}\tag{1} \end{equation} LHS variables must satisfy $\left\{\begin{array}{rcl} \ds{m + k \geq r \geq 0} & \ds{\implies} & \left\{\begin{array}{l} \ds{r \geq 0 } \\[2mm] \ds{k \geq r - m \geq -m} \end{array}\right. \\[1mm] \ds{n - k \geq s \geq 0} & \ds{\implies} & \left\{\begin{array}{l} \ds{s \geq 0 } \\[2mm] \ds{k \leq n - s \leq n} \end{array}\right. \end{array}\right.$

---

Then, \begin{align} &\color{#f00}{\sum_{k = -m}^{n}{m + k \choose r}{n - k \choose s}} = \sum_{k = r - m}^{n - s}{m + k \choose r}{n - k \choose s} = \sum_{k = r - m}^{\infty}{m + k \choose r}{n - k \choose s} \\[5mm] = &\ \sum_{k = 0}^{\infty}{m + \pars{k + r - m} \choose r} {n - \pars{k + r - m} \choose s} = \sum_{k = 0}^{\infty}{k + r \choose k} {m + n - r - k \choose m + n - r - k - s} \\[5mm] = &\ \sum_{k = 0}^{\infty}{-r - 1 \choose k}\pars{-1}^{k} {-s - 1 \choose m + n - r - s - k}\pars{-1}^{m + n - r - s - k} \\[5mm] = &\ \pars{-1}^{m + n + r + s}\sum_{k = 0}^{\infty}{-r - 1 \choose k} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s - k + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s + 1}} \sum_{k = 0}^{\infty}{-r - 1 \choose k}z^{k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s + 1}} \pars{1 + z}^{-r - 1}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1 - r - 1} \over z^{m + n - r - s + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{m + n + r + s}{-s - r - 2 \choose m + n - r - s} \\[5mm] = &\ \pars{-1}^{m + n + r + s}{s + r + 2 + m + n - r - s - 1 \choose m + n - r - s} \pars{-1}^{m + n - r - s} \\[5mm] = &\ {m + n + 1 \choose m + n - r - s} = {m + n + 1 \choose \bracks{m + n + 1} - \bracks{m + n - r - s}} = \color{#f00}{m + n + 1 \choose r + s + 1} \end{align}