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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
Ah, this is a splenid way to look at this, very intuitive. I undestand completely. Thank you kindly! – Rozemarijntje Mar 24 '14 at 20:48

Your Answer


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.