# How to prove the following combinatorial identity?

How does one prove that, for $1 \leq k \leq n$, it is true that $\binom{n+k-1}{n-1} = \sum_{i=1}^{k} \binom{k-1}{i-1} \binom{n}{i}$ ?

I tried to prove it by working out the definitions of the binomial coefficient, but to no avail. Can you please explain me how to prove this statement? Or give me a hint?

-
It should be $-1$ in the LHS binomial coefficient - the other guy from your class got it right :) –  mathse Mar 24 '14 at 20:36
Yup you two are both right, I made a mistake. –  Max Muller Mar 24 '14 at 20:40
Duplicate of math.stackexchange.com/questions/725205/… –  R. J. Mathar Mar 25 '14 at 16:44

Rewrite the right-hand side as $$\sum_{i=1}^k \binom{k-1}{i-1} \binom{n}{n-i}.$$

Now imagine we have $n$ men and $k-1$ women, and we want to count the number of ways to choose $n-1$ of these people. The left-hand side is the number of ways to do this, $\binom{n+k-1}{n-1}$ (we choose $n-1$ out of $n+k-1$ people). The right-hand side also counts the number of ways to do this, since the summand for $i$ is the number of ways to choose $i-1$ women and $n-i$ men. Since both sides count the same thing, equality must hold.

-

It becomes easier if you first recognise that you may rename $k-1$ to $k'$ and $i-1$ to $i'$, so that you need to prove $$\binom{n+k'}{n-1}=\sum_{i'=0}^{k'}\binom{k'}{i'}\binom n{i'+1}, \qquad\text{for 0\leq k'<n}$$ then apply symmetry on the last binomial coefficient, drop the primes, and write $n-1=m$ $$\binom{k+n}m=\sum_{i=0}^k\binom ki\binom n{m-i}.$$ Now you see it is the Vandermonde identity. Both sides express the coefficient of $X^m$ in $(1+X)^{k+n}=(1+X)^k(1+X)^n$. Or the number of ways to select $m$ elements out of $k+n$ that happen to be coloured so that $k$ are blue and $n$ are red. The relations between $k,n,m$ are unimportant.

-

Compare the coefficients of $x^{j-1}$ from \begin{align} (1+x)^{k-1}(1+x)^n &=\sum_{i=1}^k\binom{k-1}{i-1}x^{i-1}\sum_{j=0}^n\binom{n}{j}x^j\\ &=\sum_{i=1}^k\sum_{j=i}^{n+i}\binom{k-1}{i-1}\binom{n}{j-i}x^{j-1}\\ &=\sum_{j=1}^{n+k}\sum_{i=1}^j\binom{k-1}{i-1}\binom{n}{j-i}x^{j-1} \end{align} and $$(1+x)^{n+k-1}=\sum_{j=1}^{n+k}\binom{n+k-1}{j-1}x^{j-1}$$ to get that $$\sum_{i=1}^j\binom{k-1}{i-1}\binom{n}{j-i}=\binom{n+k-1}{j-1}$$ Plug in $j=n$, to get $$\sum_{i=1}^n\binom{k-1}{i-1}\binom{n}{n-i}=\binom{n+k-1}{n-1}$$ Since $\binom{n}{n-i}=\binom{n}{i}$, we get $$\sum_{i=1}^n\binom{k-1}{i-1}\binom{n}{i}=\binom{n+k-1}{n-1}$$

-

Yes, both answers are perfect, but to add to Marc van Leeuwen's answer - the formula is merely a simple application of the Vandermonde convolution, which states that

$\binom{n+m}{r} = \sum_{i+j=r} \binom{n}{i}\binom{m}{j}$

(with $m=k-1$ and $r=n-1$). So, from this you see that many other 'fancy' formulas also hold, such as

$\binom{n+k-1}{n-1} = \sum_{i=1}^{k-4}\binom{k-5}{i-1}\binom{n+4}{n-i}$,

etc.

-