"Stars and Bars" summation identity

Question

Can anybody help me solve this problem? I don't even know where to start or how to interpret this.

Proof for all $1 \leq k \leq n$ that the folowing identity holds:

\begin{equation*} \begin{pmatrix} n+k-1 \\ n-1 \end{pmatrix} = \sum_{i=1}^k \begin{pmatrix}k-1 \\ i-1 \end{pmatrix} \begin{pmatrix} n \\ i \end{pmatrix} \end{equation*}

This problem is in fact a homework assignment, so it would be kind if the solution isn't spoiled right away. There is one hint given in the assignment that says that for k identical objects and n different colors ($k \geq n$) the amount of different color combinations (you may repeat colors) when using every color at least once, is equal to: $\begin{pmatrix} k-1 \\ n-1 \end{pmatrix}$

I hope that anybody can assist me.

Thanks in advance!

Answer 1

Rewrite $\binom{n}{i}$ as $\binom{n}{n-i}$ and use a combinatorial proof of Vandermonde's identity.

Answer 2

Hint: Well, the RHS is choosing some color ($i$ of them) and coloring $k$ objects with those $i$ colors. Using the hint given, every of the $i-$th colors chosen is used at least once. But notice that you choose the colors, that means the other $n-i$ were not used. So, if you were to consider the $n$ colors at a whole, then you are relaxing the condition of at least once to no restriction at all. What is, then, the LHS?