Constructing A Combinatorial Proof of a Binomial Identity Consider: 
$$\sum_{k=0}^m \binom{n+k}k = \binom{m+n+1}m.$$
The LHS counts the number of subsets whose size is equal to its maximal element plus some fixed value.  Alternatively, we can choose how many ways there are to pick a subset of the maximum size $k=m$ from the maximal set $m+n+1.$  However, I am at a loss as to what to do with this information.
 A: 'Subsets of what?' seems a reasonable question to ask. Your interpretation is a little confused; the largest set considered on the LHS is one smaller than that on the right, and you don't know the subset's maximal element on the LHS, only the largest it could be.
Given what you say about the RHS, let $S = \{1, 2, \cdots, n-1, n, n+1, \cdots, n+m+1\}$. Then the RHS is the number of possible size $m$ subsets.
For the LHS, proceed as follows:


*

*How many of the subsets do not contain $(n+m+1)$? Which $k$ does this correspond to?

*How many subsets do contain $(n+m+1)$, but not $(n+m)$?

*How many subsets do contain $(n+m+1)$ and $(n+m)$, but not $(n+m-1)$?

*...


Check all subsets fall into one of these categories.
A: The RHS is in how many ways I can pick $m$ balls out of $m+n+1$.
Consider the solution:
I choose a ball. If I pick it we are left with $\binom{m+n}{m-1}$ if I don't pick it I'm let with $\binom{m+n}{m}$.
From this the recursive relation follows that:
$$\binom{m+n+1}{m} = \binom{m+n}{m} + \binom{m+n}{m-1}$$ 
Now if I continue to apply the same rule for the $\binom{m+n}{m-1}$ I'll get that sum.
In a combinatorial statement this will be the number of ways I can pick $m$ balls out of $m+n+1$ is the number of ways I can pick $m$ balls out of $m+n$ given I don't pick ball 1, plus the number of ways if I can pick $m-1$ balls out of $m+n-1$ given I pick ball 1, but not ball 2, plus the number of ways if I can pick  $m-2$ balls out of $m+n-2$ given I pick ball 1 and 2, but not 3,plus ... until I get to given I pick the first m balls and I'm done.
A: We want to find the number of ways to sum $n$ numbers, $x_1, x_2, x_3 \ldots x_n \ge 0 $, such that it is less than or equal $m$. That is:
$$ x_1 + x_2 + x_3 + \ldots + x_n \le m $$
One way to do this is to add a slack variable called $x_{n+1}$, so that $x_1 + x_2 + x_3 + \ldots + x_{n} + x_{n+1} = m $. There are $\binom{m + n}{m}$ ways to solve this equation.
Another way to do this is to consider all the ways to sum these $n$ numbers to $0, 1, 2, \ldots m-1, m$, and add up all these combinations. There are $\displaystyle\sum_{k=0}^{m} \binom{k+n-1}{k} $ ways to do so.
Your answer follows from letting $n \mapsto n+1$.
