Combinatorics identity proof by induction

Question

Prove the formula by induction on n and fixed r:

$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$

What I tried:

Base:

we take $n=r$ so $\binom{r}{r} = \binom{r + 1}{r+1} = 1$

Step: Assume that the formula holds for some $n = k$, let's show that it must hold for $n=k+1$ too. for $n=k$

$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{k}{r} = \binom{k+1}{r+1}$

for $n=k+1$

$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{k}{r} + \binom{k+1}{r}= \binom{k+2}{r+1}$.

Using the induction hypothesis:

$\binom{k+1}{r+1} + \binom{k+1}{r}= \binom{k+2}{r+1}$.

Now, I am stuck on how to transform the LHS into the RHS. I think that it has something to do with Pascal's identity, but I cannot see how I can use it.

Answer 1

Pascal's identity is $$ \binom{n-1}{m}+\binom{n-1}{m-1}=\binom{n}m $$ Let $n=k+2$, $m=r+1$.

Answer 2

$$\binom{k+1}{r+1} + \binom{k+1}{r}= \binom{k+2}{r+1}$$ $$\begin{align} \frac{(k+1)!}{(r+1)!\cdot(k-r)!}+\frac{(k+1)!}{(r)!\cdot(k-r+1)!}&= \frac{(k+1)!}{(r)!\cdot(k-r)!}\cdot\left( \frac{1}{r+1}+\frac{1}{k-r+1}\right)\\ &=\frac{(k+1)!}{(r)!\cdot(k-r)!}\cdot\left( \frac{k-r+1+r+1}{(k-r+1)(r+1)}\right)\\ &=\frac{(k+1)!}{(r)!\cdot(k-r)!}\cdot\left( \frac{k+2}{kr+k-r^2-r+r+1}\right)\\ &=\frac{(k+1)!}{(r)!\cdot(k-r)!}\cdot\left( \frac{k+2}{kr+k-r^2+1}\right)\\ &=\frac{(k+1)!}{(r)!\cdot(k-r)!}\cdot\left( \frac{k+2}{(k-r+1)(r+1)}\right)\\ &=\frac{(k+1)!\cdot(k+2)}{(r)!\cdot(r+1)\cdot(k-r)!\cdot(k-r+1)}\\ &=\frac{(k+2)!}{(r+1)!\cdot(k-r+1)!}\\ &=\binom{k+2}{r+1}\\ \end{align} $$ $$\binom{k+1}{r+1} + \binom{k+1}{r}= \binom{k+2}{r+1}$$