How can I prove this formula: $\sum_{a_1+a_2+\cdots +a_m\le n}\prod_{i=1}^ma_i=\binom{n+m}{2m}$?

Question

Take $a_1,a_2,\cdots,a_m$ balls sequentially from a box of n balls, and you don't have to take all of them. It is guaranteed that $1\le m\le n$.

Denote the product of $a_1,a_2,\cdots ,a_m$ as $\prod_{i=1}^ma_i$ .

Prove that $\binom{n+m}{2m}=\frac{(n+m)!}{(2m)!(n-m)!}$ is the sum of $\prod_{i=1}^ma_i$ for all possible $a_1,a_2,\cdots ,a_m$ sequences. That is to prove

$$ \sum_{a_1+a_2+\cdots +a_m\le n}\prod_{i=1}^ma_i=\binom{n+m}{2m} $$

where $a_1,a_2,\cdots ,a_m$ and $m, n$ are all positive integers, and $m \le n$.

Answer 1

This can be proven by induction over $m$. The base case is $m = 1$ and is obvious. To establish $m + 1$ given $m$ one only needs to check that (verify this!) $$ \sum_{k=1}^{n-m} k \binom{n + m - k}{2m} = \binom{n + m + 1}{2m + 2}. $$ (Note that above $k$ indicates the value of $a_{m+1}$ and the coefficient arises from the induction hypothesis at $m$.)

To establish the identity above, expand. Re-indexing the sum, we find (check!) $$\sum_{k=1}^{n-m} k \binom{n + m - k}{2m} = \sum_{j=1}^{n-m} \binom{2m + (n - m -j) + 1}{2m + 1} = \sum_{j=0}^{n-m - 1} \binom{2m + 1 + j}{2m + 1} = \binom{n +m + 1}{2m +2}. $$ This proves the claim. Above, we have repeatedly used the rising sum identity for binomial coefficients.

Answer 2

A solution using binomial series $(1-z)^{-m-1}=\sum_{n\geqslant 0}\binom{m+n}{m}z^n$ and generating functions. \begin{align} S_{m,n}&:=\sum_{\substack{a_1,\ \dots,\ a_m>0\\a_1+\dots+a_m\leqslant n}}\prod_{k=1}^m a_k; \\\sum_{n\geqslant m}S_{m,n}z^n&=\sum_{n\geqslant m}\sum_{\substack{a_1,\ \dots,\ a_m>0\\a_1+\dots+a_m\leqslant n}}z^n\prod_{k=1}^m a_k \\&=\sum_{a_1,\ \dots,\ a_m>0}\sum_{n\geqslant a_1+\dots+a_m}z^n\prod_{k=1}^m a_k \\&=\sum_{a_1,\ \dots,\ a_m>0}\frac{z^{a_1+\dots+a_m}}{1-z}\prod_{k=1}^m a_k \\&=\frac1{1-z}\left(\sum_{a>0}^\infty az^a\right)^m=\frac{z^m}{(1-z)^{2m+1}} \\&=z^m\sum_{k\geqslant 0}\binom{2m+k}{2m}z^k=\sum_{n\geqslant m}\binom{m+n}{2m}z^n. \end{align}