Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

4 Answers 4

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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