combinatorial argument and by induction proof Let n be a fixed natural number. Show that:
$$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$
(A): using a combinatorial argument and (B): by induction on $m$?
 A: For (A), you're supposed to find something to count that can be counted in two ways. One should be naturally representable as $\sum_{r=0}^m \binom {n+r-1}r$, and the other as $\binom{n+m}{m}$. Since it is the same thing you counted the two must be equal.
For the other you need to check that it is actually true for a few low-number cases. Then show that if it is true in any given case, then it must be true in the next case.
If you want a better answer, you should first add some personal flair to the question. Tell us how you came by it, why you want a solution, and most importantly, what you have tried yourself. Many people on this site (me includeed) are put off by askers just copying the text of a problem, including the commanding language ("Show that", rather than "how do I show that"). Also, if we don't know what you have tried yourself it is difficult to tailor a solution for you, which is what we strive to do here.
A: Finding this combinatorial argument isn’t altogether straightforward if you’ve not yet had much experience. The righthand side is easy to interpret: it’s the number of ways of choosing $m$ numbers from the set $[n+m]=\{1,2,\dots,n+m\}$. Similarly, each term on the lefthand side is easy to interpret: $\binom{n+r-1}r$ is the number of ways of choosing $r$ numbers from the set $[n+r-1]$. What’s not so clear is how to relate the two.
Suppose that I choose my set $S$ of $m$ integers from the set $[n+m]$. Let $k$ be the largest integer that I don’t choose: $k=\max\left([n+m]\setminus S\right)$. The other $n-1$ numbers not in $S$ must all be smaller than $k$, and there are $k-1$ positive integers smaller than $k$, so $S$ must contain $(k-1)-(n-1)=k-n$ members of the set $[k-1]$ of positive integers less than $k$. Thus, there are $\binom{k-1}{k-n}$ ways to choose the part of $S$ below $k$. And since $k$ is the largest number not in $S$, the rest of $S$ is already known: it’s $\{k+1,\dots,n+m\}$. Thus, the total number of ways of choosing an $m$-element subset of $[n+m]$ must be
$$\sum_k\binom{k-1}{k-n}\;.$$
To finish the combinatorial argument, answer the following questions:


*

*What is the range of possible values of $k$?  

*What is the relationship between my $k$ and the $r$ of the problem?



The proof by induction is very standard and very straightforward; the only tool that you need for the induction step is Pascal’s identity.
A: For the sake of completeness I add option (C): using generating functions.
We have
$$\sum_{r=0}^m \binom{n+r-1}{r} = 
\sum_{r=0}^m [z^n] \frac{z}{(1-z)^{r+1}} =
[z^{n-1}] \sum_{r=0}^m \left(\frac{1}{1-z}\right)^{r+1} \\ =
[z^{n-1}] \frac{1}{1-z} \frac{1-1/(1-z)^{m+1}}{1-1/(1-z)} =
[z^{n-1}] \frac{1-1/(1-z)^{m+1}}{1-z-1} =
[z^{n-1}] \frac{1}{z} \left(\frac{1}{(1-z)^{m+1}}-1\right) \\ =
[z^n]  \left(\frac{1}{(1-z)^{m+1}}-1\right).$$
Now there are two cases: first, for $m=0$, we obtain
$$ [z^n]  \left(\frac{1}{(1-z)^1}-1\right) =1 = \binom{n+m}{m}.$$
For $m\ge 1$, and keeping in mind that $n$ is a natural number, we get
$$[z^n]  \left(\frac{1}{(1-z)^{m+1}}-1\right) =
[z^{n+1}] \frac{z}{(1-z)^{m+1}} = \binom{n+1+m-1}{m} =  \binom{n+m}{m}.  $$
