# Proving $\sum\limits_{k=0}^{\infty}\binom {m-r+s}k\binom {n+r-s}{n-k}\binom {r+k}{m+n}=\binom rm\binom sn$

Question: How do you show the following equality holds using binomials$$\sum\limits_{k=0}^{\infty}\binom {m-r+s}k\binom {r+k}{m+n}\binom {n+r-s}{n-k}=\binom rm\binom sn$$

I would like to prove the identity using some sort of binomial identity. The right-hand side is the coefficient of $x^m$ and $y^n$ in\begin{align*}a_{m,n} & =\left[x^m\right]\left[y^n\right](1+x)^r(1+y)^s\\ & =\binom rm\binom sn\end{align*}

However, I don’t see how the left-hand side can be proven using the binomials. Using the generalized binomial theorem, we get the right-hand side as

\begin{align*}(1+x)^r(1+y)^s & =\sum\limits_{k\geq0}\sum\limits_{l\geq0}\binom rk\binom slx^ky^l\end{align*}However, what do I do from here?

\begin{align} &\sum_{k=0}^\infty\binom{m-r+s}{k}\binom{r+k}{m+n}\binom{n+r-s}{n-k}\\ &=\sum_{k=0}^\infty\sum_{j=0}^\infty\binom{m-r+s}{k}\binom{k}{j}\binom{r}{m+n-j}\binom{n+r-s}{n-k}\tag1\\ &=\sum_{k=0}^\infty\sum_{j=0}^\infty\binom{m-r+s}{j}\binom{m-r+s-j}{k-j}\binom{r}{m+n-j}\binom{n+r-s}{n-k}\tag2\\ &=\sum_{j=0}^\infty\binom{m-r+s}{j}\binom{m+n-j}{n-j}\binom{r}{m+n-j}\tag3\\ &=\sum_{j=0}^\infty\binom{m-r+s}{j}\binom{m+n-j}{m}\binom{r}{m+n-j}\tag4\\ &=\sum_{j=0}^\infty\binom{m-r+s}{j}\binom{r-m}{n-j}\binom{r}{m}\tag5\\ &=\binom{s}{n}\binom{r}{m}\tag6 \end{align} Explanation:
$(1)$: Vandermonde's Identity applied to the sum in $j$
$(2)$: $\binom{m-r+s}{k}\binom{k}{j}=\binom{m-r+s}{j}\binom{m-r+s-j}{k-j}$
$(3)$: Vandermonde's Identity applied to the sum in $k$
$(4)$: $\binom{m+n-j}{n-j}=\binom{m+n-j}{m}$
$(5)$: $\binom{m+n-j}{m}\binom{r}{m+n-j}=\binom{r-m}{n-j}\binom{r}{m}$
$(6)$: Vandermonde's Identity applied to the sum in $j$

With OP asking for formal power series in the evaluation of

$$\sum_{k\ge 0} {m-r+s\choose k} {r+k\choose m+n} {n+r-s\choose n-k}$$

we write

$$[z^n] (1+z)^{n+r-s} [w^{m+n}] (1+w)^r \sum_{k\ge 0} {m-r+s\choose k} z^k (1+w)^k \\ = [z^n] (1+z)^{n+r-s} [w^{m+n}] (1+w)^r (1+z+zw)^{m-r+s} \\ = [z^n] (1+z)^{n+r-s} [w^{m+n}] (1+w)^r \sum_{q=0}^{m-r+s} {m-r+s\choose q} (1+z)^{m-r+s-q} z^q w^q \\ = \sum_{q=0}^{m-r+s} {m-r+s\choose q} {m+n-q\choose n-q} {r\choose m+n-q}.$$

Note that

$${m+n-q\choose n-q} {r\choose m+n-q} = \frac{r!}{(n-q)! \times m! \times (r+q-m-n)!} \\ = {r\choose m} {r-m\choose n-q}.$$

We thus have

$${r\choose m} \sum_{q=0}^{m-r+s} {m-r+s\choose q} {r-m\choose n-q} \\ = {r\choose m} [z^n] (1+z)^{r-m} \sum_{q=0}^{m-r+s} {m-r+s\choose q} z^q \\ = {r\choose m} [z^n] (1+z)^{r-m} (1+z)^{m-r+s} = {r\choose m} {s\choose n}.$$

This is the claim.

• Sorry for the necro-post, but is there a collection of these infinite binomial sums? I'm trying to generate larger sums that are similar as the one in the question using the same methodology. Sep 16, 2021 at 6:12
• There is this list of Egorychev method / method of coefficients applications. It is not limited to binomial coefficients. Sep 16, 2021 at 17:24
• I'm mainly looking for identities similar to the ones in the question though: infinite sum, composed of binomials, closed form is a product of binomials. I'm trying to derive more identities using the same process you've demonstrated in your answer, but every time I try, it ends up simplifying to the sum in the question; was wondering if there were others Sep 17, 2021 at 3:53
• Another list is H. W. Gould's Combinatorial identities. Sep 17, 2021 at 17:07

Premise

Let's first see which are the series corresponding to the basic manipulations involved in the algebraic demonstration of the identity in question.

1) Convolution \eqalign{ & \left( {1 + yx} \right)^{\,r} \left( {1 + x} \right)^{\,s} = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} { \left( \matrix{ r \cr j \cr} \right)\,\left( \matrix{ s \cr k \cr} \right)x^{\,j} y^{\,j} \;x^{\,k} } } = \cr & = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} { \left( \matrix{ r \cr j \cr} \right)\,\left( \matrix{ s \cr k + j - j \cr} \right)x^{\,j + k} y^{\,j} } } = \cr & = \sum\limits_{0\, \le \,l} {\left( {\sum\limits_{0\, \le \,j} { \left( \matrix{ r \cr j \cr} \right)\,\left( \matrix{ s \cr l - j \cr} \right)y^{\,j} } } \right)x^{\,l} } \cr} in which, of course, one can put $x$ and/or $y$ to $1$, or other value.

2) Trinomial Revision

Trinomial Revision does not have a single z-Transform for the repeated index, but the double one is quite simple \eqalign{ & \left( {1 + y\left( {1 + x} \right)} \right)^{\,r} = \cr & = \sum\limits_{0\, \le \,k} {\left( \matrix{ r \cr k \cr} \right)y^{\,k} \left( {1 + x} \right)^{\,k} } = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,m\,\left( { \le \,k} \right)} {\left( \matrix{ r \cr k \cr} \right)\left( \matrix{ k \cr m \cr} \right)y^{\,k} x^{\,m} } } = \cr & = \left( {1 + y + yx} \right)^{\,r} = \cr & = \sum\limits_{0\, \le \,m} {\left( \matrix{ r \cr m \cr} \right)\left( {yx} \right)^{\,m} \left( {1 + y} \right)^{\,r - m} } = \sum\limits_{0\, \le \,j} {\sum\limits_{0\, \le \,m} {\left( \matrix{ r \cr m \cr} \right)\left( \matrix{ r - m \cr j \cr} \right)y^{\,m} y^{\,j} x^{\,m} } } = \cr & = \sum\limits_{m\, \le \,m + j} {\sum\limits_{0\, \le \,m} {\left( \matrix{ r \cr m \cr} \right)\left( \matrix{ r - m \cr \left( {m + j} \right) - m \cr} \right)y^{\,\left( {m + j} \right)} x^{\,m} } } = \sum\limits_{0\, \le \,\left( {m\, \le } \right)\,k} {\sum\limits_{0\, \le \,m} {\left( \matrix{ r \cr m \cr} \right)\left( \matrix{ r - m \cr k - m \cr} \right)y^{\,k} x^{\,m} } } \cr}