Combinatorial argument for an identity

Question

Consider the following equation:

$x_1 + x_2 + \cdots + x_r = n,~~$ where $~~0\leq x_{i}\leq n, \forall i$

The number of integral solutions to the above equation = ${n+r-1 \choose r-1}$.

Consider the following result:

$\Sigma_{n=0}^{N} {n+r-1\choose r-1} = {N+r \choose r}$

The above result can be proved using induction. Is there an algebraic way of proving the above result? More importantly, is there an intuitive "combinatorial argument" that justifies the above result?

Answer 1

Regarding your second question, $\binom{N+r}{r}$ is the number of outcomes of selecting $r$ integers from $\{1,2,\ldots,N+r\}$. Suppose we want to organize these outcomes by the maximum integer selected. To count the number of outcomes whose maximum integer is $n+r$, then we need to select $r-1$ other integers from $\{1,\ldots, n+r-1\}$, so there are $\binom{n+r-1}{r-1}$ such outcomes. Adding up over all possible maximums $r,r+1,\ldots,N+r$, we have $\sum_{n=0}^N \binom{n+r-1}{r-1}$.

---

To see the connection to your first question, see the hint by Johannes. To count all possible ways to satisfy $x_1+\cdots+x_r=n$, you can organize them by the possible ways $x_1+\cdots+x_{r-1} \le n$.

Answer 2

We have $N+r$ different doughnuts lined up in a row. How many ways can we choose $r$ of them for breakfast? We count this in two different ways.

The simple way gives $\binom{N+r}{r}$. We now count in a more complicated way.

Suppose that the $r$-th doughnut is the rightmost one chosen. Then there are $\binom{0+r-1}{r-1}$ ways to choose the remaining $r-1$ doughnuts.

Suppose that the $(1+r)$-th doughnut is the rightmost one chosen. Then there are $\binom{1+r-1}{r-1}$ ways to choose the remaining $r-1$ doughnuts.

Suppose that the $(2+r)$-th doughnut is the rightmost one chosen. Then there are $\binom{2+r-1}{r-1}$ ways to choose the remaining $r-1$ doughnuts.

And so on. Finally, if the $(N+r)$-th doughnut is the rightmost one chosen, there are $\binom{N+r-1}{r-1}$ to choose the remaining $r-1$ doughnuts.

Add up.

Answer 3

You asked about an algebraic proof. Consider the identity $$(1+x)^{-1} \cdot (1+x)^{-r} = (1+x)^{-r-1}$$ Expand everything by the Binomial Theorem for negative exponents: $$\sum_{i=0}^{\infty} x^i \cdot \sum_{n=0}^{\infty} \binom{r+n-1}{r-1} x^n= \sum_{N=0}^{\infty} \binom{r+N}{r} x^N$$ The coefficient of $x^N$ on the left hand side is $\sum_{n=0}^N \binom{r+n-1}{r-1}$; the coefficient on the right hand side is $\binom{r+N}{r}$.