2

I'm having trouble generating a combinatorial proof for the following equality: $$\sum_{i=0}^{r} ({m \choose i}) = {{m + r}\choose m}.$$ That is, with no algebraic manipulation, what is an "example" that would sufficiently illustrate what these expressions are doing?

Here is my attempt at an answer:

RHS: we have m distinguishable items of item type A, and $r$ distinguishable items of item type B. The number of ways to choose $m$ items from this combination of item type A and item type B is ${m + r} \choose m$.

LHS: there are $r + 1$ disjoint cases for which $r$ indistinguishable items are being categorized into $m$ distinguishable categories. And here is where I have trouble conceptualizing what the disjoint cases are.

Would really appreciate some help understanding conceptually why LHS equals RHS!

LackLuster
  • 29
  • 4

2 Answers2

1

We can prove this by using the following equation: $\binom{m}{n}=\binom{m-1}{n}+\binom{m-1}{n-1}$

$\sum_{i=0}^r\left(\binom mi\right)=\sum_{i=0}^r\binom{m+i-1}{i}=\binom{m-1}{0}+\sum_{i=1}^r\binom{m+i-1}{i}=\binom{m}{0}+\sum_{i=1}^r\binom{m+i-1}{i}=\binom{m}{0}+\binom{m}{1}+\sum_{i=2}^r\binom{m+i-1}{i}=\binom{m+1}{1}+\sum_{i=2}^r\binom{m+i-1}{i}=\binom{m+2}{2}+\sum_{i=3}^r\binom{m+i-1}{i}=\cdot\cdot\cdot=\binom{m+r}{r}=\binom{m+r}{m}$

we prove the equality by applying $\binom{m}{n}=\binom{m-1}{n}+\binom{m-1}{n-1}$ repeatedly.

yifan dai
  • 106
0

Here's a quick combinatorial proof, inspired by wikipedia's article on the hockey stick identity.

A committee of size $m$ from $m+r$ people can be formed in $$\binom{m+r}{m}$$ ways. Now pass out the numbers $0,1,2,3,...,r$ to $r+1$ of the $m+r$ people. Now here are your $r+1$ disjoint cases. In case $i$ with $0 \leq i \leq r$, person $i$ is on the committee and persons $0,1,2,...i-1$ are not on the committee. This can be done in $$\binom{m+r-i-1}{m-1}=\binom{m+r-i-1}{r-i}$$ ways. Now we can write $$\binom{m+r}{m}=\sum_{i=0}^r\binom{m+r-i-1}{r-i}=\sum_{i=0}^r\binom{m+i-1}{i}=\sum_{i=0}^r \left(\binom{m}{i}\right)$$

The only real bit of manipulation comes here in the form of $$\left(\binom mi \right) = \binom{m+i-1}{i}$$ but this can be shown combinatorially as well through stars and bars.

Isaac Browne
  • 8,076