Do I use induction or is there another way to prove $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$?

Question

Prove the following statement is true: $$\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$$.

Since $\binom{r}{r}=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$, is that to form a basis step? If so, how do I induce k+1 for n+1 and r+1 (where n ≥ r and both positive integers)? At the same time, or in two steps?

Answer 1

You can prove this combinatorially without induction. Hint: consider the $(r+1)$-sets from $\{1, \ldots, n+1\}$, grouped by their largest element.

Answer 2

You prove the theorem for any given $r$ it by induction on $k = n-r$. The basis is $$ \binom{r}{r}=\binom{r+1}{r+1} $$ which is true sine $1=1$. Now assume that $$ \sum_{m=0}^k \binom{r+m}{r} = \binom{r+k+1}{r+1} $$ Then examine $$ \binom{r+k+2}{r+1} - \binom{r+k+1}{r+1}= \frac{r+k+2-(k+1)}{r+1} \binom {r+k+1}{r} $$ as can be seen by writing out the factorials and factoring out the common part. This is in fact $$\frac{r+1}{r+1} \binom {r+k+1}{r} $$ which then shows $$ \sum_{m=0}^k \binom{r+m}{r} +\binom{r+k+1}{r} =\sum_{m=0}^{k+1} \binom{r+m}{r} =\binom{r+m+2}{r+1} $$ establishing induction.