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!

  • 1
    $\begingroup$ Note: the double bracket notation (( )) indicates multichoose! $\endgroup$ – LackLuster Feb 13 '18 at 3:40
  • $\begingroup$ For those who don't know: $$ \left(\binom mi \right) = \binom{m+i-1}{i} $$ $\endgroup$ – Omnomnomnom Feb 13 '18 at 3:52

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.