0
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

$$\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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.$

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.