# Really need help with combinatorial proof!

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.

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

$$\binom{m-1}{0}+\binom{m}{1}+\binom{m+1}{2}+\cdots+\binom{m+r-1}{r}.$$

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.

 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.

• 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! – xonian Feb 16 '17 at 7:08
• Ah, I see. Have added a combinatorial reason. – Especially Lime Feb 16 '17 at 7:21
• Awesome, thank you so much. – 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}