combinatorics - Prove that $C(n,0) + C(n+1,1) +dots+ C(n+r,r) = C(n+r+1,r).$

I am not even sure where to start with this question. Any help would be much appreciated! Thanks!
We are not allowed to use Mathematical Induction!

Answer

First, note that $\binom{m}{i} = \binom{m}{m-i}$, so we can rewrite your equality into
$$\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+r}{n} = \binom{n+r+1}{n+1}$$

And here is my interpretation: you have $n+r+1$ numbered balls, and you want to pick $n+1$ of them. This can obviously be done in $\binom{n+r+1}{n+1}$ ways.

Now, let's divide this into cases by the highest number among the balls you pick. That number cannot be less than $n+1$, obviously. Now, how many ways are there to pick $n+1$ balls so that the largest number on any of them is $n+1$? Well, you obviously have to pick ball number $n+1$. After that, you have to pick $n$ balls from the $n$ balls with lower number. That can be done in $\binom nn$ ways.

If the highest number we pick is $n+2$, how many ways can that be done? We have to pick the $n+2$ ball, and after that we need to choose $n$ balls from the $n+1$ balls that are smaller than $n+2$. That can be done in $\binom{n+1}n$ ways. And so on. Adding all these contributions together, this eventually becomes $\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+r}{n}$.

These two ways count the same number of things, and therefore the result must be the same.