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

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?

• Fix $r$ and prove by induction. Initial: $n=r$: So $\binom r r=\binom{r+1}{r+1}$. Then prove if true for $n$, true for $n+1$. – Thomas Andrews Nov 17 '14 at 0:13

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.
• Then do it by initially choosing the largest of the $r+1$ numbers.
\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}