I have spent the last few hours trying to crack this combinatorial proof and I was really hoping someone would be able to help out.

$$\sum_{i=0}^r \left(\!\!{m\choose i}\!\!\right)= \binom{m+r}{r}$$

Thank you! I have tried thinking of a counting question to pose but none of them have really seemed to fit what is given above.

Note: On the left is a multiset of m and i.

  • $\begingroup$ Why do you add the parenthesis? I've never seen that done before. $\endgroup$ – S.C.B. Feb 16 '17 at 6:57
  • $\begingroup$ To represent a multisite of m and i $\endgroup$ – xonian Feb 16 '17 at 6:58
  • $\begingroup$ And what is a multisite? Google returns no meaningful results. $\endgroup$ – S.C.B. Feb 16 '17 at 6:59
  • $\begingroup$ I'm sorry, multiset - my autocorrect messed that one up $\endgroup$ – xonian Feb 16 '17 at 6:59
  • $\begingroup$ Oh, that's what it is. I would think a better $\LaTeX$ for that would be \left(\!\!{n\choose k}\!\!\right). $\endgroup$ – S.C.B. Feb 16 '17 at 7:01

Use the formula that $\left(\!{n\choose k}\!\right)=\binom{n+k-1}{k}$ to get


Now note that $\binom{m-1}0=\binom m0$, so $\binom{m-1}0+\binom{m}1=\binom m0+\binom m1=\binom{m+1}1$. Keep using this identity and the whole sum will collapse.

[edit] A combinatorial proof:

The RHS is the number of ways to choose a multiset of size $r$ from $n+1$ objects. There is a one-to-one correspondence between such multisets and possible multisets of size at most $r$ taken from the first $n$ objects -- just throw away any copies of object $n+1$ we may have chosen. This is what the LHS counts.

  • $\begingroup$ that's actually how I went about it originally, but I need to prove it with combinatorially, or with some sort of counting question, rather than algebraic expansion or manipulation, which is where I am stuck. Thank you though! $\endgroup$ – xonian Feb 16 '17 at 7:08
  • $\begingroup$ Ah, I see. Have added a combinatorial reason. $\endgroup$ – Especially Lime Feb 16 '17 at 7:21
  • $\begingroup$ Awesome, thank you so much. $\endgroup$ – xonian Feb 16 '17 at 7:33

$$\begin{align} \sum_{i=0}^r \left(\!\!{m\choose i}\!\!\right) &=\sum_{i=0}^r\binom{m+i-1}{m-1}\\ &=\sum_{i=0}^r\binom{m-1+i}{m-1}\\ &=\binom{m-1+r+1}{m-1+1}\\ &= \binom{m+r}{m}\\ &=\binom {m+r}r \end{align}$$


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.