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}$ I want to show that the following holds:
$$\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}.$$
I have an idea of what is going on here. On the RHS we are selecting $r+s+1$ elements from the set $[m+n+1]$. Another way of doing this is to partition the set $[m+n+1]$ into two sets in several ways by shifting $k$ elements from one set to the other. For example, we can partition $[m+n+1]$ into a set with $m+k$ elements and a set with $n+1-k$ elements. From the set with $m+k$ elements we can select $r$ elements and from the set with $n+1-k$ elements we can select $s+1$. However, this is not matching the LHS. I believe the problem is that we don't know which $k$ elements are being shifted around.
I thought rewriting the sum as follows would help:
$$\sum_{k=0}^{m+n} \binom{k}{r} \binom{n+m-k}{s}.$$
I just don't understand why the "$+1$" on the top and bottom of the RHS disappear. I have spent several hours on this problem, and I have run out of ideas. Please help, I truly appreciate it.
 A: $\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}
A: Suppose we seek to evaluate
$$\sum_{k=-m}^n {m+k\choose r} {n-k\choose s}
= \sum_{k=0}^{m+n} {k\choose r} {m+n-k\choose s}.$$
Here we may assume that $r$ and $s$ are non-negative. We introduce
$${m+n-k\choose s} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-k-s+1}} \frac{1}{(1-z)^{s+1}} \; dz.$$
This integral  controls the range, being  zero when $k\gt  m+n$ and we
may extend the range of $k$ to infinity. We get for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-s+1}} \frac{1}{(1-z)^{s+1}} 
\sum_{k\ge 0} {k\choose r} z^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-s+1}} \frac{1}{(1-z)^{s+1}} 
\sum_{k\ge r} {k\choose r} z^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-s+1}} \frac{z^r}{(1-z)^{s+1}} 
\sum_{k\ge 0} {k+r\choose r} z^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-s+1}} \frac{z^r}{(1-z)^{s+1}} 
\frac{1}{(1-z)^{r+1}}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{m+n-r-s+1}} \frac{1}{(1-z)^{r+s+2}} 
\; dz.$$
We get for the answer
$${m+n-r-s+r+s+1\choose r+s+1}
= {m+n+1\choose r+s+1}.$$
