A combinatorial sum via generating series? I would like to prove that $$\sum_{k=0}^{n} {k \choose m} {n-k \choose r-m} = {n+1 \choose r+1}$$
holds for all $n \in \mathbb{N}$ and $0 \leq m < r \leq \frac{n}{2}$. It seems that you may be able to use generating functions, with the Cauchy product, but I am not really sure on the details. I would like an algebraic proof of this.
 A: If we look at the sum, at first glance it seems that we can say, Choose $m$ of the first $k$ items, and $r-m$ of the remaining $n-k$ items, so in all we choose $r$ of $n$ items."  There's some double counting going on though.  When there are a string of unchosen items, which $k$ should the selection count against.
Having seen the problem, we fix it easily.  Let item $k+1$ be the $m+1$st item chosen.  Then choose $m$ of the items before it, and and $r-m$ of the items after it.  This cover all ways to choose $r+1$ items out of $n+1$ and only those ways.
A: We seek to verify that
$$\sum_{k=0}^n {k\choose m} {n-k\choose r-m}
= {n+1\choose r+1}$$
where $n\ge 0$ and $0\le m \le n$ and $m\le r\le n.$
We get for the LHS
$$\begin{align*}
& [z^m] [w^{r-m}] \sum_{k=0}^n
(1+z)^k (1+w)^{n-k}
\\ & = [z^m] [w^{r-m}] (1+w)^n \sum_{k=0}^n
(1+z)^k (1+w)^{-k}
\\ & = [z^m] [w^{r-m}] (1+w)^n
\frac{(1+z)^{n+1}/(1+w)^{n+1}-1}{(1+z)/(1+w)-1}
\\ & = [z^m] [w^{r-m}] (1+w)^n
\frac{(1+z)^{n+1}/(1+w)^{n}-(1+w)}{z-w}
\\ & = [z^m] [w^{r-m}]
\frac{(1+z)^{n+1}-(1+w)^{n+1}}{z-w}
\end{align*}.$$
Now we have
$$\frac{(1+z)^{n+1}-(1+w)^{n+1}}{z-w}
= \sum_{q=0}^n {n+1\choose q+1} \sum_{p=0}^q z^p w^{q-p}.$$
This is because the RHS is
$$\begin{align*}
& \sum_{q=0}^n {n+1\choose q+1} w^q \sum_{p=0}^q z^p/w^p
= \sum_{q=0}^n {n+1\choose q+1} w^q
\frac{z^{q+1}/w^{q+1}-1}{z/w-1}
\\ & = \sum_{q=0}^n {n+1\choose q+1} w^q
\frac{z^{q+1}/w^{q}-w}{z-w}
= \sum_{q=0}^n {n+1\choose q+1}
\frac{z^{q+1}-w^{q+1}}{z-w}
\\ & = \frac{1}{z-w}
\left[ \sum_{q=0}^n {n+1\choose q+1} z^{q+1}
- \sum_{q=0}^n {n+1\choose q+1} w^{q+1}
\right]
\\ & = \frac{1}{z-w}
\left[ \sum_{q=-1}^n {n+1\choose q+1} z^{q+1}
- \sum_{q=-1}^n {n+1\choose q+1} w^{q+1}
\right]
\\ & = \frac{1}{z-w} \left[(1+z)^{n+1}-(1+w)^{n+1}\right].
\end{align*}$$
Returning to the main sum we now see that it is given by
$$[z^m] [w^{r-m}]
\sum_{q=0}^n {n+1\choose q+1} \sum_{p=0}^q z^p w^{q-p}
= [z^m] [w^{r-m}]
\sum_{p=0}^n \frac{z^p}{w^p}
\sum_{q=p}^n {n+1\choose q+1} w^q.$$
With $m\le n$ we obtain
$$[w^{r-m}] \frac{1}{w^m}
\sum_{q=m}^n {n+1\choose q+1} w^q
= [w^r] \sum_{q=m}^n {n+1\choose q+1} w^q.$$
With $m\le r\le n$ this becomes at last
$$\bbox[5px,border:2px solid #00A000]{
{n+1\choose r+1}.}$$
The concluding step also follows by inspection seeing that
$p=m$ and $q=r$ are the only combination $z^p w^{q-p}$ that can
possibly contribute to $[z^m] [w^{r-m}].$
A: Here is a plain algebraic derivation.

We obtain
\begin{align*}
\color{blue}{\sum_{k=0}^n\binom{k}{m}\binom{n-k}{r-m}}&=\sum_{k=m}^{n-r+m}\binom{k}{m}\binom{n-k}{r-m}\tag{1}\\
&=\sum_{k=0}^{n-r}\binom{m+k}{k}\binom{n-m-k}{n-r-k}\tag{2}\\
&=\sum_{k=0}^{n-r}\binom{-m-1}{k}\binom{m-r-1}{n-r-k}(-1)^{n-r}\tag{3}\\
&=\binom{-r-2}{n-r}(-1)^{n-r}\tag{4}\\
&\,\,\color{blue}{=\binom{n+1}{r+1}}\tag{5}
\end{align*}
and the claim follows.

Comment:

*

*In (1) we set lower and upper index skipping terms which do not contribute to the sum.


*In (2) we shift the index to start with $k=0$ and use $\binom{p}{q}=\binom{p}{p-q}$.


*In (3) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ twice.


*In (4) we apply Chu Vandermonde's identity.


*In (5) we use the binomial identities from (2) and (3) again.

Note the nice nearly reciprocal relationship with the more familiar identity
\begin{align*}
\sum_{k=0}^n\binom{m}{k}\binom{r-m}{n-k}=\binom{r}{n}
\end{align*}

A: Fix $m$ and $r$, and use a generating function with respect to $n$:
\begin{align}
\sum_{n \ge 0} \sum_{k=m}^{n-r+m} \binom{k}{m} \binom{n-k}{r-m} z^n 
&= \sum_{k \ge m} \binom{k}{m} z^k \sum_{n\ge k+r-m} \binom{n-k}{r-m} z^{n-k} \\
&= \sum_{k \ge m} \binom{k}{m} z^k \frac{z^{r-m}}{(1-z)^{r-m+1}} \\
&= \frac{z^{r-m}}{(1-z)^{r-m+1}} \sum_{k \ge m} \binom{k}{m} z^k \\
&= \frac{z^{r-m}}{(1-z)^{r-m+1}} \cdot \frac{z^m}{(1-z)^{m+1}} \\
&= \frac{z^r}{(1-z)^{r+2}} \\
&= \frac{1}{z}\cdot\frac{z^{r+1}}{(1-z)^{r+2}} \\
&= \frac{1}{z} \sum_{n \ge r} \binom{n+1}{r+1} z^{n+1} \\
&= \sum_{n \ge r} \binom{n+1}{r+1} z^n \\
&= \sum_{n \ge 0} \binom{n+1}{r+1} z^n
\end{align}
Note that this "snake oil" approach derives the RHS of the desired identity without knowing it ahead of time.
