Proof: $\binom{x+y+n-1}{n} = \sum_{k=0}^{n} \binom{x+n-k-1}{n-k} \binom{y+k-1}{k}$

Question

I wanted to prove following equation $\binom{x+y+n-1}{n} = \sum_{k=0}^{n} \binom{x+n-k-1}{n-k} \binom{y+k-1}{k}$

Using Vandermonde's identity $\binom{a+b}{t} = \sum_{k=0}^{t} \binom{a}{t-k} \binom{b}{k}$

whereas $a=x+n-k-1$ and $b=y+k-1$ but it doesn't add up.

Where is my mistake? How do i proof it?

Answer 1

It seems that the identity is a repeated combination version of Vandermonde's identity. Let us denote the number of ways to choose $k$ objects out of $n$ objects allowing repetition as $_n H _k$. Recall that the formula for the repeated combination is given as $_n H_k = \binom{n+k-1}{k}.$ Now your identity is equivalent to $_{x+y} H_{n} = \sum_k ~_{x} H_{n-k} \cdot _{y} H_{k}$. This identity can be proved by reasoning as in the proof of Vandermonde's identity. Suppose that there are $x$ red balls and $y$ blue balls, and you choose $n$ balls among them allowing repetition. The number of ways to do so is clearly $_{x+y} H_n$. On the other hand, if you want to choose $n$ balls so that $(n-k)$ of them are red and $k$ of them are blue, there are $_x H_{n-k} \cdot _y H_{k}$ ways to do so. Summing over $k = 0 \cdots n$, you have the right-hand side.

Answer 2

That's called "double convolution": we have $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,n\,} {\left( \matrix{ a + k \cr k \cr} \right)\left( \matrix{ b - k \cr n - k \cr} \right)} \quad \left| \matrix{ \,a,b \in \mathbb C \hfill \cr \;0 \le n \in \mathbb Z \hfill \cr} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)\,} {\left( \matrix{ a + k \cr k \cr} \right)\left( \matrix{ b - k \cr n - k \cr} \right)} = \quad \quad (1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)\,} {\left( { - 1} \right)^{\,k} \left( \matrix{ - a - 1 \cr k \cr} \right)\left( { - 1} \right)^{\,n - k} \left( \matrix{ n - b - 1 \cr n - k \cr} \right)} = \quad \quad (2) \cr & = \left( { - 1} \right)^{\,n} \left( \matrix{ n - a - b - 2 \cr n \cr} \right) = \quad \quad (3) \cr & = \left( \matrix{ a + b + 1 \cr n \cr} \right) \quad \quad (4) \cr} $$ where:
(1) we can omit the sum bounds because they are implicit in the binomials, this simplifies the algebraic manouvres;
(2) upper negation;
(3) Vandermonde convolution;
(4) upper negation again.

Answer 3

We have for our sum

$$\sum_{k=0}^n {x+n-k-1\choose n-k} {y+k-1\choose k} \\ = [z^n] (1+z)^{x+n-1} \sum_{k=0}^n {y+k-1\choose k} z^k (1+z)^{-k}.$$

The coefficient extractor controls the range of the sum:

$$[z^n] (1+z)^{x+n-1} \sum_{k\ge 0} {y+k-1\choose k} z^k (1+z)^{-k} \\ = [z^n] (1+z)^{x+n-1} \frac{1}{(1-z/(1+z))^y} \\ = [z^n] (1+z)^{x+n-1} (1+z)^y = [z^n] (1+z)^{x+y+n-1} \\ = {x+y+n-1\choose n}$$

as claimed.