Sum of product of binomial coefficient

Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$

I tried to use the multinomial theorem, but it doesn't seem applicable.

Solution 1:

Combinatorially the equality is obvious. Each way of picking $n$ items out of $k_1+k_2+\cdots+k_n$ items will amount to choosing $x_1$ from first $k_1$, $x_2$ from the next $k_2$, and so on all the way to $x_n$ out of last $k_n$, where the total count of items picked is $x_1+\cdots+x_n=n$ (with some summands possibly being $0$): the number of ways of doing this is ${k_1\choose x_1}{k_2\choose x_2}\cdots{k_n\choose x_n}$ because the selections are independent. Now sum over all $x_i$ with $\small\sum x_i=n$ and you're done.

This can be seen more formally with generating functions too. Write $K=k_1+\cdots k_n$ so that $$(1+u)^K=\sum_{m=0}^K{k_1+\cdots+k_n\choose m}u^m$$ which is also equal to $$(1+u)^{k_1}(1+u)^{k_2}\cdots(1+u)^{k_n}=\large\prod_{i=1}^n\left(\sum_{\ell_i=0}^{k_i}{k_i\choose\ell_i}u^{\ell_i}\right)$$ so that the coefficient of $u^m$ (note this is more general than just the $m=n$ case) is the product of all factors of the form ${k_i\choose\ell_i}$ with $0\le\ell_i\le\ k_i$ where the $\ell_i$'s all add up to $m$. Note however that if $\ell_i>k_i$ the binomial coefficient is $0$ and so it makes no difference if we also add in the products of factors with any of the $\ell_i$'s breaking the inequality: in other words we can write $$=\large\sum_{m=0}^K\left(\sum_{\ell_1+\cdots+\ell_n=m}\;\;\prod_{i=1}^n{k_i\choose\ell_i}\right)u^m.$$ Equating the coefficients gives the desired equality.