0
$\begingroup$

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

I'm confused how to start this question. Would it require induction?

$\endgroup$

marked as duplicate by N. F. Taussig combinatorics Nov 20 '17 at 22:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Yes, you can prove this by induction on $n$ where we fix an $r$.

So fix $r\in\Bbb N$. The base case is for $n=r$, which I will leave for you to verify (but this is fairly easy). Now we use the induction hypothesis which says that $\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}$ and we want to show that $\sum_{k=r}^{n+1}\binom{k}{r}=\binom{n+2}{r+1}$. This follows almost immediately from the addition formula on binomial coefficients (aka. Pascal's identity) which gives $$\binom{n+2}{r+1}=\binom{n+1}{r+1}+\binom{n+1}{r}$$I leave it to you to piece it all together.

$\endgroup$

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