Combinatorial proof of binomial coefficient summation

Question

While doing some Computer Science problems, I found one which I thought could be solvable using combinatorics instead of programming:

Given two positive integers $n$ and $k$, in how many ways do $k$ numbers, all of which are between $0$ and $n$ (inclusive), add up to $n$?

In the problem, order does matter. For example, 0+20 is not equivalent to 20+0. This led me to the following solution:

Assume you do want to create the sum without any of the terms being zero. Then, the problem can be looked at as if you have $n$ rocks, and you want know the number of ways you can place $k-1$ sticks between them, such that no stick may be placed between the same two rocks. This is obviously equal to $\binom{n-1}{k-1}$.

If you then want to count the number of ways you can create the sum with exactly one of the terms being zero. Then the solution is (number of ways to get to $n$ using $k-1$ non-zero terms)*(the number of ways we can choose 1 element among k). Then, when wanting to count the number of ways with exactly $x$ zeroes, the answer is (number of ways to get to n using $k-x$ non-zero terms)*(the number of ways we can choose $x$ elements among $k$).

The solution to the original problem will basically the sum of the above expression, with x ranging between $0$ and $k-1$ (since there needs to be at least 1 non-zero term).

This leads to $\displaystyle\sum_{i=0}^{k-1}\left[ \binom{n-1}{k-i-1}\binom{k}{i}\right]$

I later went on to search on Google if there existed any simpler solution, and found that $\binom{n+k-1}{n}$ worked as well, but without explanation and proof.

Both solutions give the same answer for any positive $n$ and $k$, but I really have trouble understanding why. I've tried to simplify my summation, and proving it inductively, but I have not been successful.

Could somebody help me prove the equality?

$\binom{n+k-1}{n} = \displaystyle\sum_{i=0}^{k-1}\left[ \binom{n-1}{k-i-1}\binom{k}{i}\right]$

Answer 1

Taking your rocks and sticks example, your basic question is how many ways are there to place $n$ rocks and $k-1$ sticks in order as each pattern (of the rocks) is one solution to your problem. This is ${n+k-1 \choose n}$.

If $n=1$ then all your discussion of $i$ zero terms will come out at $0$ except when $i=k-1$ and in that case you will have $\left[ \binom{0}{0}\binom{k}{k-1}\right] = k$, so you do not need to distinguish $n=1$ in your expression.

Answer 2

There is no need to break into cases concerning the existence of piles of "0 rocks". A pile of zero rocks can be represented by having two "sticks" between the same two rocks (between those two sticks there are zero rocks!). Indeed, I can represent any number of consecutive piles of zero rocks by having the appropriate number of sticks between the same two rocks.

So, with that in mind, I am really looking to count the number of ways that I can place $k-1$ sticks among $n$ rocks. (By the way, why does this representation still retain the ordering? Try finding sticks and rocks representations of $0 + 20$ and $20 + 0$, and other combinations.) Now, this is equivalent to choosing from $n + k - 1$ objects, exactly $n$ of them to be our "rocks" (leaving the other $k-1$ to be our "sticks"). And there are $\binom{n+k-1}{n}$ ways to do that.

Hope this helps!