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


  • 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.