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

• Not that it entirely corresponds to your question, but this may be of a little help, away the use of Binomial Theorem: math.stackexchange.com/questions/2381429/… – Tony Hellmuth Jun 12 '18 at 3:44
• @TonyHellmuth It’s certainly similar, but I’m not sure what the $s$ in the lower-limit indicates. Is it from zero to infinity, of is it a finite sum? – Frank W. Jun 12 '18 at 4:13

## 3 Answers

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.

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

• right: that is in line with the explanation I gave in previous answer to this related post – G Cab Jun 12 '18 at 17:40

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}

Your Request

Considering the requirement of your post, if we take the expansion already given in the related post, which is equivalent to that given above by robjohn, and attempt to go backwards, we will realize that we are going into a complicated formal series involving some five or six variables, which does not seem to be much of interest.
That's mainly due to the Trinomial Revision asking for a double sum.

The first step in such a backward route was already given in the answer to the cited related post.

• Sorry, I'm still kind of confused. Just give me some time; still processing everything! :) – Frank W. Jun 18 '18 at 4:01