Give the combinatorial proof of the identity $\sum\limits_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Question

Given the identity

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

Need to give a combinatorial proof

a) in terms of subsets

b) by interpreting the parts in terms of compositions of integers

I should not use induction or any other ways...

Please help.

Answer 1

HINTS:

1. Consider a $k$-element subset of $[n+k]=\{1,\dots,n+k\}$; it has a maximum element, which can be anything from $k$ through $n+k$. How many such subsets are there with maximum element $k+i$ for $i=0,\dots,n$?

2. There are $\binom{k-1+i}{k-1}$ compositions of $k+i$ with $k$ terms. There are $\binom{n+k}k$ compositions of $n+k+1$ with $k+1$ terms.