I tried to solve this formula. I was asked to use a recursive solution.
I need to find a recursive formula to the number of possibilities to choose the color of k balls from n colors (every ball must have a color):
This, in order to prove the next phrase:
$$ \binom{n+k}{n} = \sum_{i=0}^{k}\binom{n+i-1}{n-1} $$
Thank you for your time!
Let's call your number $b_{n,k}$. The recurrence you want is $$b_{n,k+1} = b_{n,k} + \binom{n+k}{n-1}.$$ After that, your formula follows by induction on $k$, because $b_{n,k} = \binom{n+k}{n}$.
Hint for proving the recurrence: you need to show that $b_{n,k+1}-b_{n,k} = \binom{n+k}{n-1}$.
That is, you need to show that the number of ways to choose the color of $n$ balls out of $k+1$ colors such that at least one ball has the last color is $\binom{n+k}{n-1}$. Does that inspire a stars-and-bars style solution?
