combinatorics - A generalized combinatorial identity for a sum of products of binomial coefficients

I have the following question.

For given natural numbers $n$ and $d$, let $a_1,a_2,..., a_r$ be fixed integers such that $a_1+\cdots+a_r=d$. Let $A=\{(i_1,..,i_r)~|~0\le i_j\le n~ \text{and}~ i_1+\cdots+i_r=n\}$.

$$\underset {(i_1,...,i_r)\in A} \sum {i_1\choose a_1}{i_2\choose a_2}\cdots{i_r\choose a_r}= {n+r-1\choose d+r-1}$$

Is the above combinatorial identity true ? I know that this is true when $r$ is $2$.

Answer

Yes, it is true. To show this, use induction on $r$. (As you say, it's true for $r=2$ and obviously, it's also true for $r=1$). Then

$$\sum_{(i_1,\ldots,i_r)\in A}\binom{i_1}{a_1}\cdots \binom{i_r}{a_r}=\sum_{i_r=0}^n\sum_{\stackrel{i_1+\cdots+i_r=n}{0\le i_1,\ldots,i_{r-1}\le n}}\binom{i_1}{a_1}\cdots \binom{i_{r-1}}{a_{r-1}}\binom{i_r}{a_r}=\sum_{i_r=0}^n\binom{i_r}{a_r}\sum_{\stackrel{i_1+\cdots+i_{r-1}=n-i_r}{0\le i_1,\ldots,i_{r-1}\le n}}\binom{i_1}{a_1}\cdots\binom{i_{r-1}}{a_{r-1}}.$$

Using the induction hypothesis, this equals

$$\sum_{i_r=0}^n\binom{i_r}{a_r}\binom{n-i_r+r-2}{d-a_r+r-2},$$

and then applying the case $r=2$ (i.e., when you have two summands $j_1+j_2=m$ and $b_1+b_2=e$) yields that the latter is equal to

$$\binom{n-i_r+r-2+i_r+(2-1)}{d-a_r+r-2+a_r+(2-1)}=\binom{n+r-1}{d+r-1}$$

as requested.

---

EDIT To clarify, the case $r=2$ is the statement

$$\sum_{\stackrel{a+b=m}{0\le a,b\le m}}\binom{a}{x}\binom{b}{y}=\binom{a+b+1}{x+y+1},$$

the LHS of which is equal to

$$\sum_{b=0}^m\binom{b}{x}\binom{m-b}{y}.$$