Prove that $\sum_{0\leq k\leq r} \binom{n+k}{k} \binom{m+n+k}{n+k} = \binom{m+n}{n} \binom{m+n+r+1}{m+n+1}$ where $m,n,r\in \mathbb{N} $ $\sum_{0\leq k\leq r} \binom{n+k}{k} \binom{m+n+k}{n+k} = \binom{m+n}{n} \binom{m+n+r+1}{m+n+1}$ where  $m,n,r\in \mathbb{N} $. 
Exam problem which stayed unproven for me. I tried induction/binomial properties together and separately.I also tried to find a power serie which could use these binomials. Could someone provide at least a hint? 
 A: Induction always works for hypergeometric sum identities.
$r=0$: $$\sum_{k=0} \binom{n+k}{k} \binom{m+n+k}{n+k} = \binom{m+n}{n} = \binom{m+n}{n} \binom{m+n+r+1}{m+n+1}$$
$r > 0$: $$\begin{eqnarray}
\textrm{LHS} &=& \binom{m+n}{n} \binom{m+n+(r-1)+1}{m+n+1} + \binom{n+r}{r} \binom{m+n+r}{n+r} \\
&=& \binom{m+n}{n} \frac{(m+n+r)!}{(m+n+1)!(r-1)!} + \frac{(m+n+r)!}{n!r!m!} \\
&=& \binom{m+n}{n} \left[ \frac{(m+n+r)!}{(m+n+1)!(r-1)!} + \frac{(m+n+r)!}{(m+n)!r!} \right] \\
&=& \binom{m+n}{n} \left[ \frac{(m+n+r)!r + (m+n+r)!(m+n+1)}{(m+n+1)!r!} \right]\\
&=& \binom{m+n}{n} \left[ \frac{(m+n+r)!(r+m+n+1)}{(m+n+1)!r!} \right]\\
&=& \binom{m+n}{n} \left[ \frac{(m+n+r+1)!}{(m+n+1)!r!} \right]\\
&=& \binom{m+n}{n} \binom{m+n+r+1}{m+n+1}
\end{eqnarray}$$

Alternatively, for a combinatorial proof, both sides count the number of ways of colouring $m+n+r$ objects in a line such that $m$ are red, $n$ are blue, the rest are green or yellow, and all the yellow ones are together at the end of the line.
On the LHS, $k$ is the number of greens and the term inside the sum is a simple multinomial.
On the RHS, we take $m+n+r+1$ slots and choose $m+n+1$ of them. Colour the slots to the right of the last chosen one yellow, and the unchosen slots to its left green. Then delete that slot. From the other $m+n$ chosen slots, choose $m$ to colour red.
A: We  use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
\begin{align*}
[z^k](1+z)^n=\binom{n }{k}\tag{1}
\end{align*}

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

Comment:


*

*In (2) we use the coefficient of operator according to (1).

*In (3) we do some rearrangements and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (4) we use the finite geometric series expansion.

*In (5) we do some simplifications and apply the rule from (3) again.

*In (6) we select the coefficient of $z^r$ from $(1+z)^{m+n+r+1}$ noting that the other term $-(1+z)^{m+n}z^{r+1}$ does not contribute.
