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.
No comments:
Post a Comment