In answering someone else's question (Permutation query involving 3 people with a limit of 45 as the sum.) I came across an interesting result that wasn't immediately obvious to me:
$$\binom{n}{k} = \sum_{m=k}^{n} \binom{m-1}{k-1}$$
It basically says that the number of positive integer $k$-tuples whose sum is less than or equal to $n$ is given as $\tbinom{n}{k}$. I have not actually proven that this relationship holds, but I threw an handful of different test values at it, and the equality held.
If this is true, is there any kind of intuitive explanation as to why? I imagine that it can be proven mathematically without great effort, but I am mostly interested in a "balls and urns" or "stars and bars" type explanation, if one exists.
Best Answer
Since you mentioned stars-and-bars, note that $\sum_{m=k}^n\binom{m-1}{k-1}$ is the number of solutions in positive integers to
$$k\le x_1+x_2+\ldots+x_k\le n\;.\tag{1}$$
For any solution $\langle x_1,\ldots,x_k\rangle$ to $(1)$ let $x_{k+1}=n+1-\sum_{i=1}^kx_i\ge 1$; then
$$x_1+x_2+\ldots+x_k+x_{k+1}=n+1\tag{2}\;.$$
Conversely, if $\langle x_1,\ldots,x_{k+1}\rangle$ is a solution to $(2)$ in positive integers, then $\langle x_1,\ldots,x_k\rangle$ is a solution to $(1)$ in positive integers. Since $(2)$ has $\binom{n}k$ solutions in positive integers, we must have
$$\sum_{m=k}^n\binom{m-1}{k-1}=\binom{n}k\;.$$