# 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?

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.

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.