Show $\large\sum\limits_{j=0}^{r}\binom{j+k-1}{k-1}=\binom{r+k}{k}$

Hint: Place $r$ balls in $m$ urns, in how many of this arrangements can you find $b$ balls in the first urn.

I'm sure that there are many other methods to solve this problem, but I have to do it with the given hint.

It is clear for $r$ balls in $m$ urns the possible number of distributions is $\large\binom{r+m-1}{m}$

Now. if I have $b$ balls in the first urn, $r-b$ balls must be distributed into the remaining urns ($m-1$). Hence $\large\binom{(r-b)+(m-1)-1}{m-1}=\large\binom{r-b+m-2}{m-1}$

and summing over b from $0$ to $r$ must give the first formula;


Now I'm stuck. From this formula, I can't deduce the required identity, Is there a chance to transform it ? Thanks in advance.


For $r$ balls in $m$ urns the number of possible distributions is $\left( \array{ r + m - 1 \\ m - 1 } \right)$, not $\left( \array{ r + m - 1 \\ m } \right)$. So we see that on the left side of the equation, $\left( \array{ j + k - 1 \\ k - 1 } \right)$ is the number of ways you can distribute $j$ balls into $k$ urns, and on the right side, $\left( \array{ r + k \\ k } \right)$ is the number of ways you can distribute $r$ balls into $k + 1$ urns.

Your instinct that you should be summing $b$ over the range $0$ to $r$ was a good one, but due to the error in the formula for $r$ balls in $m$ urns, it seems you were led into trying to set $m = k$. Using the correct formula, $m = k + 1$ becomes a more obvious tactic. You have set up enough parts of the proof already that I think this will enable you to complete it.

  • $\begingroup$ Oh sh.., very stupid of me, Ok thanks. $\endgroup$ – derivative Apr 28 '14 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.