$\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?
On
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.
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.