Give the combinatorial proof of the identity $\sum\limits_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$ 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.

Alternatively, both the LHS and RHS count the number of non-negative integer solutions to the inequality $\displaystyle \sum_{r=0}^{k}x_{r} \leq n$ which can be readily seen via the double counting below:
1) From the LHS, this inequality can be written as $n+1$ equalities of the form $\displaystyle \sum_{r=0}^{k}x_{r} = i$ where $i=0,1, \ldots n$, each of which have $\displaystyle \binom{k+i-1}{k-1}$ solutions in the non-negative integers and hence the total number of solutions is $\displaystyle \sum_{i=0}^{n}\binom{k+i-1}{k-1}$.
2) From the RHS viewpoint, we can convert this inequality into an equality by adding a slack variable $x_{k+1}$ on the LHS to obtain $\displaystyle \sum_{r=0}^{k+1}x_{r} = n$ which of course has $\displaystyle \binom{n+k}{k}$ solutions in the non-negative integers.
