# Equality of the number of multisets to \sum_{i = 1}^k \binom{k - 1}{i - 1} \binom{n}{i}

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!

-

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