# How do you prove the following formula $\binom{n+i-1}{n} = \sum\limits_{k=0}^{n}\binom{i-1}{k} \binom{n}{k}\$?

I'd like to prove the following formula: For any $i, n \in \mathbb{N}^*$ $$\binom{n+i-1}{n} = \sum\limits_{k=0}^{n}\binom{i-1}{k} \binom{n}{k}\ .$$

In fact, I fixed $i \in \mathbb{N}^*$ and verified some cases of $n$. For example,

$$\binom{i+2-1}{2} = \binom{i-1}{0} + 2\binom{i-1}{1} + \binom{i-1}{2},$$ $$\binom{i+3-1}{3} = \binom{i-1}{0} +3\binom{i-1}{1} + 3 \binom{i-1}{2} + \binom{i-1}{3},$$ Can you help me?

$$\sum\limits_{k=0}^{n}\binom{i-1}{k} \binom{n}{k}=\sum\limits_{k=0}^{n}\binom{i-1}{k} \binom{n}{n-k}$$ Imagine that you are choosing $n$ balls from two boxes, one has $i-1$ balls while the another has $n$ balls. The way to choose, in one hand, is $$\binom{n+i-1}{n}$$ But on the other hand, it's $$\sum\limits_{k=0}^{n}\binom{i-1}{k} \binom{n}{n-k}$$ It's done here.

You want to select $n$ objects out of $n+i-1$ objects. You can visualize the $n+i-1$ objects as $n$ objects first, followed by $i-1$ objects.

To select your $n$ objects, you can take $k$ out of the first $n$, and then take $n-k$ out of the following $i-1$. This can be done for any $0\le k \le n$.

Now take the sum over $k$.

Here's an algebraic answer using generating functions. For convenience let $m = i-1$, so we are trying to prove $$\binom{n+m}{n} = \sum\limits_{k=0}^{n}\binom{m}{k} \binom{n}{k}\ .$$ By the binomial theorem, the lefthand side is the coefficient of $x^n$ in $(1+x)^{n+m}$. Since $\binom{n}{k} = \binom{n}{n-k}$, the convolution formula for polynomials tells us that the righthand side is the coefficient of $x^n$ in $(1+x)^m (1+x)^n$. (This "convolution formula" is just the fact that the coefficient of $x^n$ in the product $\left(\sum_{i=0}^r a_i x^i\right) \left(\sum_{i=0}^s b_i x^i\right)$ is $\sum_{k=0}^n a_k b_{n-k}$.) Since $(1+x)^m (1+x)^n = (1+x)^{n+m}$, then the two sides are equal.

In symbols, we can write this as follows: \begin{align*} \binom{n+m}{n} &= [x^n] (1+x)^{n+m} = [x^n] (1+x)^{n} (1+x)^{m} = \sum_{k=0}^{n} \left([x^k] (1+x)^{n} \cdot [x^{n-k}](1+x)^{m}\right)\\ &= \sum\limits_{k=0}^{n}\binom{m}{k} \binom{n}{n-k} = \sum\limits_{k=0}^{n}\binom{m}{k} \binom{n}{k} \, , \end{align*} where $[x^n]f(x)$ denotes the coefficient of $x^n$ in the polynomial $f$.

You may immediately prove it observing that it is a particular case of the Chu-Vandermonde identity $$\dbinom{x+a}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{a}{n-k}.$$ In fact, taking $$a=n,\,x=i-1$$ and observing that $$\dbinom{n}{n-k}=\dbinom{n}{k}.$$ we get $$\sum_{k=0}^{n}\dbinom{i-1}{k}\dbinom{n}{n-k}=\sum_{k=0}^{n}\dbinom{i-1}{k}\dbinom{n}{k}=\color{red}{\dbinom{n+i-1}{n}}.$$ Another simple way is to use the Egorychev representation $$\dbinom{n}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{k+1}}dz$$ then we have $$\dbinom{n+i-1}{n}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n+i-1}}{z^{n+1}}dz$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{n+1}}\sum_{k=0}^{i-1}\dbinom{i-1}{k}z^{k}dz=\sum_{k=0}^{i-1}\dbinom{i-1}{k}\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{n-k+1}}dz$$ $$=\sum_{k=0}^{i-1}\dbinom{i-1}{k}\dbinom{n}{n-k}=\color{blue}{\sum_{k=0}^{n}\dbinom{i-1}{k}\dbinom{n}{n-k}}$$ where the last identity follows from the observation that if $k>n$ then $\dbinom{n}{n-k}=0.$

It's just the Vandermonde's identity. Notice that $$\sum_{k=0}^n \binom {i-1}{k}\binom {n}{k}=\sum_{k=0}^n \binom {i-1}{k}\binom {n}{n-k}$$ Then by Vandermonde's identity we get $$\sum_{k=0}^n \binom {i-1}{k}\binom {n}{n-k}=\binom {n+i-1}{n}$$