Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $? I can't resolve this exercise and I need a tip.
$$ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $$
where $ n \geq s $.
 A: Apply the following in order:


*

*symmetry to get the summation index $k$ to appear at the bottom

*upper negation  to remove $k$ from the top

*Vandermonde's identity to settle the summation and remove $k$

*upper negation to make $r, s$ appear at the top

*symmetry to remove $r, s$ from the bottom.

A: Suppose we seek to evaluate
$$\sum_{k=0}^r {r-k\choose m} {s+k\choose n}$$
where $n\ge s$ and $m\le r.$
Introduce
$${r-k\choose m}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{r-k-m+1}} \frac{1}{(1-z)^{m+1}}  \; dz.$$
Note that this is zero when $k\gt r-m$ so we may extend the sum in $k$
to $k=\infty.$
Introduce furthermore
$${s+k\choose n}
=  \frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{(1+w)^{s+k}}{w^{n+1}} \; dw.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+1}}  
\frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{(1+w)^{s}}{w^{n+1}} 
\sum_{k\ge 0} z^k (1+w)^k
\; dw\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+1}}  
\frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{(1+w)^{s}}{w^{n+1}} 
\frac{1}{1-(1+w)z}
\; dw\; dz.$$
For the  geometric series  to converge we  must have  $|z(1+w)|\lt 1$,
which also  ensures that  the inner  pole is  not inside  the contour.
Observe that $|z(1+w)|  = \epsilon |1+w| \le  \epsilon (1+\gamma).$ So
we  need to  choose $1+\gamma  \lt  1/\epsilon$ with  $\epsilon$ in  a
neighborhood of zero. The  choice $\epsilon=1/2$ and $\gamma=1/2$ will
work.
Continuing we find
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+2}}  
\frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{(1+w)^{s}}{w^{n+1}} 
\frac{1}{1-wz/(1-z)}
\; dw\; dz.$$
Extracting the inner residue we get
$$\sum_{q=0}^n {s\choose n-q} \frac{z^q}{(1-z)^q}.$$
Now 
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{r-m-q+1}} \frac{1}{(1-z)^{m+q+2}}  \; dz
= {r+1\choose m+q+1}$$
which yields for the sum
$$\sum_{q=0}^n {s\choose n-q} {r+1\choose m+q+1}.$$
Continue  by re-indexing for
$$\sum_{q=0}^s {s\choose q} {r+1\choose m+n-q+1}$$
where we have lowered the upper  limit to $s$ since the first binomial
coefficient is zero when $q\gt s.$
Using
$${r+1\choose m+n-q+1} = 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{r+1}}{z^{m+n-q+2}} dz$$
we thus obtain for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{r+1}}{z^{m+n+2}}
\sum_{q=0}^s {s\choose q} z^q dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{r+s+1}}{z^{m+n+2}}
= {s+r+1\choose n+m+1}.$$
Remark. This can be done using formal power series only.
We have for the sum
$$\sum_{k=0}^r {r-k\choose m} {s+k\choose n}
= \sum_{k=0}^r 
[z^{r-k-m}] \frac{1}{(1-z)^{m+1}}
[w^n] (1+w)^{s+k}
\\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}}
[w^n] (1+w)^{s}
\sum_{k=0}^r z^k (1+w)^k.$$
Now  we may  certainly  extend the  sum  to infinity  as  there is  no
contribution to the coefficient extractor when $k\gt r-m$ (recall that
$r\ge m$) getting
$$[z^{r-m}] \frac{1}{(1-z)^{m+1}}
[w^n] (1+w)^{s}
\sum_{k\ge 0} z^k (1+w)^k
\\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}}
[w^n] (1+w)^{s} \frac{1}{1-z(1+w)}
\\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}}
[w^n] (1+w)^{s} \frac{1}{1-z-wz}
\\ = [z^{r-m}] \frac{1}{(1-z)^{m+2}}
[w^n] (1+w)^{s} \frac{1}{1-wz/(1-z)}.$$
Now with $n\ge s$ we get for the inner coefficient
$$\sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n-q}}.$$ 
Substitute into the outer coefficient extractor to get
$$[z^{r-m}] \frac{1}{(1-z)^{m+2}}
\sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n-q}}
= [z^{r-m}]
\sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n+m+2-q}}
\\ = \sum_{q=0}^s {s\choose q} 
[z^{r-m-n+q}] \frac{1}{(1-z)^{n+m+2-q}}
= \sum_{q=0}^s {s\choose q} 
{r+1\choose n+m+1-q}
\\ = \sum_{q=0}^s {s\choose q} 
[z^{n+m+1-q}] (1+z)^{r+1}
= [z^{n+m+1}] (1+z)^{r+1}
\sum_{q=0}^s {s\choose q} z^q
\\ = [z^{n+m+1}] (1+z)^{r+1} (1+z)^s
= [z^{n+m+1}] (1+z)^{r+s+1}
= {r+s+1\choose n+m+1}.$$
A: Let's count in how many ways one can choose $m+n+1$ numbers $a_1<a_2<\cdots <a_{m+n+1}$ out of $\{1,2,\cdots, r+s+1\}$?
Since $n\ge s$, one can only choose $a_{n+1}$ from $\{s+1,\cdots, s+r+1\}$. For each value $a_{n+1}=s+k+1$, one then continue to choose $a_1<a_2<\cdots<a_n\leq s+k$ and... 
