10
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

5
$\begingroup$

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

$\endgroup$
2
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Frank W
    Sep 16, 2021 at 6:12
  • $\begingroup$ There is this list of Egorychev method / method of coefficients applications. It is not limited to binomial coefficients. $\endgroup$ Sep 16, 2021 at 17:24
  • $\begingroup$ 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 $\endgroup$
    – Frank W
    Sep 17, 2021 at 3:53
  • $\begingroup$ Another list is H. W. Gould's Combinatorial identities. $\endgroup$ Sep 17, 2021 at 17:07
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .