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

Question

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.

Answer 1

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.

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

Answer 2

$$\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}$$