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:


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.


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

  • $\begingroup$ thank you, I knew I was missing something really obvious :S $\endgroup$ – LearnToMath Oct 23 '14 at 6:43

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


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.