# Proving that $\binom{r}{r} + \binom{r + 1}{r} + \cdots + \binom{n}{r} = \binom{n + 1}{r + 1}$ [duplicate]

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?

## marked as duplicate by N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Nov 20 '17 at 22:56

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.