# Identity for a sum of product of binomial coefficients

For some fixed positive integers $$r_1,\ldots,r_n$$, I would like to find a sum:

$$\sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{r_1}\cdots\binom{r_n+i_n}{r_n}=\sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{i_1}\cdots\binom{r_n+i_n}{i_n},$$

where $$k=0,\ldots,r_1+\cdots+r_n$$ ($$i_j$$ ranges from $$0$$ to $$r_j$$, for $$j=1,\ldots,n$$).

If reformulate the problem. Multiply $$n$$ finite sums:

$$\sum_{i_1=0}^{r_1}\binom{r_1+i_1}{r_1}\cdots\sum_{i_n=0}^{r_n}\binom{r_n+i_n}{r_n}$$

collect and sum parts such that $$i_1+\cdots+i_n=k$$. What is the result of every such sum.

I have found similar question here, but I can not connect it to this problem. Also found a paper which uses probabilistic method to establish several generalisations of Vandermonde identity (which to my dilettante view is somewhat similar to my problem).

Here is a small example just to be clear what I want to achieve. Let $$n=3$$ and $$r_1=1$$, $$r_2=2$$, $$r_3=3$$. Now take $$k=3$$, it takes six combinations of $$(i_1,i_2,i_3)$$: $$(1,1,1)$$, $$(1,2,0)$$, $$(1,0,2)$$, $$(0,1,2)$$, $$(0,2,1)$$, $$(0,0,3)$$ so that $$i_1+i_2+i_3=k$$ (note that $$i_1, i_2, i_3$$ can take values at most $$1$$, $$2$$ and $$3$$ respectively). So the sum is:

\begin{align*} &&{2\choose1}{3\choose2}{4\choose3}+{2\choose1}{4\choose2}{3\choose3}+{2\choose1}{2\choose2}{5\choose3}+\\ &&{1\choose1}{3\choose2}{5\choose3}+{1\choose1}{4\choose2}{4\choose3}+{1\choose1}{2\choose2}{6\choose3}=\\ &&24+12+20+30+24+20=130. \end{align*}

• you put "$i_j$ ranges from $0$ to $r_j$" : is that an actual requirement ? Jul 7 '20 at 19:22
• $k=0$ when all $i_j=0$ and $k=r_1+\cdots+r_n$ when $i_1=r_1,\ldots,i_n=r_n$. For some fixed value of $k$, take all possible combinations of $i_1,\ldots,i_n$ so that they sum up to $k$. Jul 8 '20 at 5:53
• In your example you forgot the following combinations: $(2,0,1),(2,1,0),(3,0,0),(0,3,0)$. Taking them into account the result will be $165$.
– user
Jul 8 '20 at 11:21
• @user Please note, that $i_1,\ldots,i_n$ can take values at most $r_1,\ldots,r_n$ respectively. Jul 8 '20 at 11:58
• Sorry. I have overlooked this additional requirement.
– user
Jul 8 '20 at 12:38

Here is what can be obtained with generating function technique:

$${r+i \choose r}=[x^i]\frac{1}{(1-x)^{r+1}}$$, where $$[x^i]f(x)$$ is the coefficient of $$x^i$$ in the power series expansion of $$f(x)$$. Then $$\sum_{i_1+\cdots+i_n=k}\binom{r_1+i_1}{r_1}\cdots\binom{r_n+i_n}{r_n}=[x^k]\frac{1}{(1-x)^{r_1+\cdots+r_n+n}}={r_1+\cdots+r_n+n-1+k \choose k}$$

• That does not hold when I take an example. For $r_1=1$, $r_2=2$, $r_3=3$ and $k=3$ it takes six combinations of $(i_1,i_2,i_3)$: $(1,1,1)$, $(1,2,0)$, $(1,0,2)$, $(0,1,2)$, $(0,2,1)$, $(0,0,3)$. And the sum is $24+12+20+30+24+20=130$. Jul 8 '20 at 6:23
• @user Please note, that $i_1,\ldots,i_n$ can take values at most $r_1,\ldots,r_n$ respectively. This example shows that the result is not Binomial coefficient. Jul 8 '20 at 11:36
• Ok then my answer is wrong, and it seems to me that the question is much more difficult given these restrictions on the $i_j$. May be investigating the case $n=2$ would give insights or new ideas. Jul 8 '20 at 18:37

So if I properly understood your question, you are looking for $$S({\bf r}_{\,n} ,m) = \sum\limits_{\left\{ {\matrix{ {0\, \le \,k_{\,j} \, \le \,r_{\,j} } \cr {\,k_{\,1} + k_{\,2} + \cdots + k_{\,n} \, = \,m} \cr } } \right.} {\left( \matrix{ r_{\,1} + k_{\,1} \cr k_{\,1} \cr} \right) \left( \matrix{ r_{\,2} + k_{\,2} \cr k_{\,2} \cr} \right) \cdots \left( \matrix{ r_{\,n} + k_{\,n} \cr k_{\,n} \cr} \right)}$$ where we can consider $${\bf r}_{\,n}$$ as a vector in $$n$$ dimensions.

If it was not for the limitation $$0\, \le \,k_{\,j} \, \le \,r_{\,j}$$ the above would be a convolution of the $$n$$ binomials, giving an ogf which is the product of $$1/(1-x)^{r_{\,j}+1 }$$ as per Renè answer.

With the excursion of $$k_{\,j}$$ limited to $$[0, \,r_{\,j}]$$ we have instead a truncated version of the above which we can express as follows. \eqalign{ & F(x,r_{\,j} ) = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,} {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } - x^{\,r_{\,j} + 1} \sum\limits_{\,0\, \le \,k\,} {\left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right)x^{\,k} } \cr}

Indicating with $$t_{\,k}$$ the coefficient in the second sum $$t_{\,k} = \left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right) = {{\left( {2r_{\,j} + 1 + k} \right)^{\,\underline {\,r_{\,j} \;} } } \over {r_{\,j} !}} = {{\left( {r_{\,j} + 2 + k} \right)^{\,\overline {\,r_{\,j} \,} } } \over {1^{\,\overline {\,r_{\,j} \,} } }}$$ we have \eqalign{ & t_{\,0} = \left( \matrix{ 2r_{\,j} + 1 \cr r_{\,j} \cr} \right) \cr & {{t_{\,k + 1} } \over {t_{\,k} }} = {{\left( {r_{\,j} + 3 + k} \right)^{\,\overline {\,r_{\,j} \,} } } \over {\left( {r_{\,j} + 2 + k} \right)^{\,\overline {\,r_{\,j} \,} } }} = {{\left( {2r_{\,j} + 2 + k} \right)} \over {\left( {r_{\,j} + 2 + k} \right)}} \cr} so one way to express a single term would be through the hypergeometric function \eqalign{ & F(x,r_{\,j} ) = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } = \sum\limits_{0\, \le \,k\, \le \,r_{\,j} } {\left( \matrix{ r_{\,j} + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,} {\left( \matrix{ r_{\,j} + k \cr k \cr} \right)x^{\,k} } - x^{\,r_{\,j} + 1} \sum\limits_{\,0\, \le \,k\,} {\left( \matrix{ 2r_{\,j} + 1 + k \cr r_{\,j} \cr} \right)x^{\,k} } = \cr & = {1 \over {\left( {1 - x} \right)^{\,r_{\,j} + 1} }} - x^{\,r_{\,j} + 1} \left( \matrix{ 2r_{\,j} + 1 \cr r_{\,j} \cr} \right) {}_2F_{\,1} \left( {\left. {\matrix{ {2r_{\,j} + 2,\;1} \cr {r_{\,j} + 2} \cr } \;} \right|\;x} \right) \cr}

But now, multiplying the terms $$G(x,{\bf r}_{\,n} ) = \sum\limits_{0\, \le \,m} {S({\bf r}_{\,n} ,m)x^{\,m} } = \prod\limits_{j = 1}^n {F(x,r_{\,j} )}$$ leads to a complicated expression.

Conclusion: lacking a "compact" form to express the truncated binomial, tere is not much to do to