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?

  • $\begingroup$ 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/… $\endgroup$ – Tony Hellmuth Jun 12 '18 at 3:44
  • $\begingroup$ @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? $\endgroup$ – Frank W. Jun 12 '18 at 4:13

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$

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


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.

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

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.