# 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.

'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.

• So the subsets that do not contain (n+m+1) correspond to n + m and then further we check those that have n+m-1, but not n+m, those with n+m-2 but not n+m-1 and so on? – 114 Apr 22 '13 at 0:32
• Added an extra line to help clarify. – Sharkos Apr 22 '13 at 0:34
• Thanks, that helped quite a bit. – 114 Apr 22 '13 at 0:40

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.

• Thanks, I see your response is very similar in style to Sharkos's. – 114 Apr 22 '13 at 0:33

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$.

• So this solution has to do with the relationship between binomial coefficients and generating functions in some sense? It's very interesting. – 114 Apr 22 '13 at 0:40
• @Stopwatch, thanks, I made up this solution myself and I'm convinced that it's pretty unique. I'm not sure exactly where you see the generating functions, however. – George V. Williams Apr 22 '13 at 0:45
• Well for a sum of n+1 elements where their sum is m the mth coefficient is $m+(n+1)-1 \choose m$ if I recall. Or rather that coefficient gives the number of ways said elements can sum to m. Is that right? – 114 Apr 22 '13 at 0:46
• @Stopwatch, yes. – George V. Williams Apr 22 '13 at 0:50