Combinatorial identity: $\sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{i}=\binom{n+k-1}{k}$

Question

How does one get to the following combinatorial identity: $$\sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{i}=\binom{n+k-1}{k}$$

I'm well aware of the definition of a multiset, as well as of the derivation of cardinalities of such. The closest one I came across is a special case of the Chu-Vandermonde identity, namely for any integers $i,k$ and $n$ satisfying $0\leq i\leq k \leq n$ the following holds true $$\sum_{m=0}^n\binom{m}{i}\binom{n-m}{k-i}=\binom{n+1}{k+1}$$

Any help is appreciated. Thanks in advance.

Answer 1

The left-hand side can be rewritten as $\sum_{i=0}^{k-1} \binom{n}{i+1}\binom{k-1}{k-1-i}$.

If the sum were $\sum_{i=-1}^{k-1}$, then applying the Vandermonde identity would yield $\binom{n+k-1}{k}$. Is there a typo?

Answer 2

We have two bags. First bag has $n$ balls, second bag has $k-1$ balls.

We pick $i+1$ balls from first bag and reject $i$ balls from second bag. So we are drawing $i+1+(k-1-i)=k$ balls in total for each $i$.

Number of ways is $$\binom{n+k-1}{k}$$

Answer 3

$$ \sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{i} =\sum_{i=0}^{k-1}\binom{n}{n-i-1}\binom{k-1}{i} =\binom{n+k-1}{n-1} =\binom{n+k-1}{k} $$

Answer 4

$n$ boys and $k-1$ girls. How many ways to pick a team of $k$?

Ignoring the gender distinction, the answer is just $\binom{n+k-1}{k}$.

The number of boys picked is between $1$ and $k$. If I pick $i+1$ boys, then I need to pick $k-i-1$ girls. So $$\binom{n+k-1}{k}=\sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{k-i-1}=\sum_{i=0}^{k-1}\binom{n}{i+1}\binom{k-1}{i}.$$