Proving that $\sum\limits_{k=0}^{n} {{m+k} \choose{k}} = { m+n+1 \choose n }$

Question

I've been trying to prove this problem for awhile now, as preparation for a test, could anyone provide a solution I could follow?

$$\sum\limits_{k=0}^{n} {{m+k} \choose{k}} = { m+n+1 \choose n }$$ for all nonnegative integers m and n.

Any help will be appreciated.

Answer 1

The upper limit should be $n$. So we have $$ \sum\limits_{k=0}^{n} {{m+k} \choose{k}} = \sum\limits_{k=0}^{n} {{m+k} \choose{m}}$$ is the coefficient of $x^m$ in $$(1+x)^m + (1+x)^{m+1}+\ldots + (1+x)^{m+n} = (1+x)^m\frac{(1+x)^{n+1}-1}{(1+x)-1} = \frac{(1+x)^{m+n+1}-(1+x)^m}{x}$$ that is, we want the coefficient of $x^{m+1}$ in $(1+x)^{m+n+1}-(1+x)^m$. The last term contributes nothing, and the first term contributes $\binom{m+n+1}{m+1} = \binom{m+n+1}{n}$ which is what you require.

Answer 2

LHS = number of $(m+1)$-element subsets of the set $\{1, 2, \ldots, n+1+m\}$. (technically, it counts the $n$-element subsets but we can consider the complement)

Now take one of these subsets $S$ and denote its largest element by $x$. Consider $x$ fixed and let us count all possible $S$ with this given $x$. We choose remaining $m$ elements of the set $\{1, \ldots, x-1\}$, so we have $\binom{x-1}{m} = \binom{x-1}{x-1-m}$ possibilities. Now, we can sum it through all possible $x=m+1, m+2, \ldots, m+1+n$. If we substitute $k=x-(m+1)$, we get exactly the RHS.