# 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}$? [duplicate]

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?

## marked as duplicate by David, Graham Kemp, user147263, Jyrki Lahtonen, Jonas MeyerNov 21 '14 at 5:07

• Assuming you mean $\binom{n}{r}$ it is horribly confusing to use the notation $(n/r)$ which looks like division. – Mark Fischler Nov 21 '14 at 4:04
You can prove this combinatorially without induction. Hint: consider the $(r+1)$-sets from $\{1, \ldots, n+1\}$, grouped by their largest element.
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.