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.

As part of an exercise I'm tasked to prove that for $1 \leq k \leq n$ \begin{align*} \binom{n + k - 1}{n - 1} = \sum_{i = 1}^k \binom{k - 1}{i - 1} \binom{n}{i} \end{align*}

I know that the left part is the number of ways $k$ elements can be chosen from $n$, without an ordering and with possible repeats. But why this equality should hold eludes me.

Entering this in Wolfram Alpha gives the equality as well, so I guess this can be obtained algebraically as well, but I haven't managed this yet. Any hints would be much appreciated, thank you in advance for any help you can offer!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Imagine that you have two groups: $n$ males, and $k-1$ females. How many ways can you pick a group of size $n-1$?

Well, you first choose how many males you don't want. This can be any number i where $1\le i\le k$. You can choose the $i$ guys you don't like in $$\binom{n}{i}$$ ways. Then, you have to take $i-1$ ladies and put them in, giving you the correct $(n-i)+(i-1)=n-1$ persons in the group. That part can be done in $$\binom{k-1}{i-1}$$ ways. Multiplying the two and summing over the possible values of $i$ yields the number of ways to pick of group of size $n-1$ from $n+k-1$ choices: $$\binom{n+k-1}{n-1}$$

share|improve this answer
    
Ah, this is a splenid way to look at this, very intuitive. I undestand completely. Thank you kindly! –  Rozemarijntje Mar 24 at 20:48

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.