Proving a combinatorics equality: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$

Question

How to prove the following? Should I use induction or something else?

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that $$\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}.$$

Attempted start:

Basis step: ${\binom{1}{1}} = {\binom{2}{2}}$ true.

Where do I go from here?

Answer 1

Here is a combinatorial proof. Consider the problem of choosing $r+1$ numbers from $1,2,\ldots,n+1$, where repetition is not allowed and order is not important.

• First do it the obvious way. The number of ways is the RHS.
• Then do it by initially choosing the largest of the $r+1$ numbers.

See if you can fill in the details.

Answer 2

Note that

$$\begin{align} \binom ab+\binom a{b+1}&=\binom{a+1}{b+1}\\ \Rightarrow \binom ab&=\binom{a+1}{b+1}-\binom a{b+1}\end{align}$$

Hence $$\begin{align} \binom ir&=\binom {i+1}{r+1}-\binom i{r+1}\\ \sum_{i=r}^n\binom ir&=\sum_{i=r}^n\binom {i+1}{r+1}-\sum_{i=r}^n\binom i{r+1}\\ &=\sum_{i=r+1}^{n+1}\binom {i}{r+1}-\sum_{i=r+1}^n\binom i{r+1}\\ &=\binom {n+1}{r+1}\qquad\blacksquare \end{align}$$