To prove for multichoose $\big(\!{{a+b}\choose k}\!\big)= \sum_{j=0}^k \big(\!{a\choose j}\!\big) \cdot \big(\!{b\choose {k-j}}\!\big)$

Question

$$\left(\!\!{{a+b}\choose k}\!\!\right)= \sum_{j=0}^k \left(\!\!{a\choose j}\!\!\right) \cdot \left(\!\!{b\choose {k-j}}\!\!\right)$$

I am quite confused about the case of multichoose. I was able to prove this equation if only "n choose k" form was used as both sides would be the k-th coefficients of $(1+x)^{a+b}$.

Any help to understand this would be very appreciated.

Answer 1

This binomial identity is an instance of the Chu-Vandermonde identity.

We start with the right-hand side. We obtain \begin{align*} \color{blue}{\sum_{j=0}^k\left(\!\!\binom{a}{j}\!\!\right)\!\!\left(\!\!\binom{b}{k-j}\!\!\right)} &=\sum_{j=0}^k\binom{a+j-1}{j}\binom{b+k-j-1}{k-j}\tag{1}\\ &=\sum_{j=0}^k\binom{-a}{j}(-1)^j\binom{-b}{k-j}(-1)^{k-j}\tag{2}\\ &=(-1)^k\sum_{j=0}^k\binom{-a}{j}\binom{-b}{k-j}\\ &=(-1)^k\binom{-a-b}{k}\tag{3}\\ &=\binom{a+b+k-1}{k}\\ &\,\,\color{blue}{=\left(\!\!\binom{a+b}{k}\!\!\right)} \end{align*} and the claim follows.

Comment:

• In (1) we use the definition of the multiset coefficient.

• In (2) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we apply the Chu-Vandermonde identity.

Note: We see from (2) and (3) the identity is in terms of generating functions with $[z^k]$ denoting the coefficient of $z^k$ in the series: \begin{align*} [z^{k}](1-z)^{-a-b}=[z^k](1-z)^{-a}(1-z)^{-b} \end{align*}

Answer 2

Consider the ways to choose any $k$ objects from two piles (of size $a$ and $b$).

One way is to simply combine the piles and choose them (the ways to do this is $\binom{a+b}k$, a.k.a. the LHS).

Another way is to first choose some, say, $j$ objects from pile $a$ (can be done in $\binom aj$ ways) and then choose the remaining $k-j$ objects from pile $b$ (can be done in $\binom b{k-j}$ ways, so this operation may be done in $\binom aj \binom b{k-j}$ ways). Adding all the cases for the different $j$s we get $\sum_{j=0}^k \binom aj \binom b{k-j}$. From the equivalence of these processes we get the result.