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?

  • $\begingroup$ 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$. $\endgroup$ – 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.

  • 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.


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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.