combination numbers induction proof

Question

Consider numbers $n \geq r \geq 1$ where $n,r \in \mathbb{Z} $, prove the following: $$\binom {r}{r} + \binom {r+1}{r}...+ \binom n r = \binom {n+1}{r+1}$$

Only thing I know is that if I choose to use induction using n choosing the base case n = r = 1 is not the way to go.

I also tried to rewrite it into the following

$$1 + \sum_{i=r+1}^n \binom i r = \binom {n+1}{r+1}$$ but that didn't really help me all that much.

Answer 1

Note that $$ \binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1} $$ Therefore repeatedly applying this in reverse, $$ \begin{split} \binom{n+1}{r+1} &= \binom{n}{r} + \binom{n}{r+1} \\ &= \binom{n}{r} + \binom{n-1}{r} + \binom{n-1}{r+1} \\ &= \binom{n}{r} + \binom{n-1}{r} + \binom{n-2}{r} + \binom{n-2}{r+1} \end{split} $$ can you finish this?

Answer 2

Idea induction for n and $$ \\{n+1 \choose k+1}={n\choose k+1}+{n\choose k} $$

Answer 3

Hint:

Rewrite Pascal's relation as $$\binom{r+i}r=\binom{r+i+1}{r+1}-\binom{r+i}{r+1}$$ and sum these relations w.r.t. $i$ to obtain a telescoping sum.

Answer 4

Base case $n=r$. Thus $$\sum_{k=r}^{n=r}\binom{k}{r}=1=\binom{r+1}{r+1}$$ For the inductive case suppose, for some $i\in\mathbb{N}\; :\; i>r$, $$\sum_r^{i}\binom{k}{r}=\binom{i+1}{r+1}$$ So $$\sum_r^{i+1}\binom{k}{r}=\Biggl(\sum_r^{i}\binom{k}{r}\Biggr)+\binom{i+1}{r}=\binom{i+1}{r+1}+\binom{i+1}{r}$$ $$=\frac{(i+1)!}{(r+1)!(i-r)!}+\frac{(i+1)!}{r!(i+1-r)!}=\frac{(i+1)!(i+1-r)}{(r+1)!(i+1-r)!}+\frac{(i+1)!(r+1)}{(r+1)!(i+1-r)!}=\frac{(i+2)!}{(r+1)!(i+1-r)!}=\binom{i+2}{r+1}$$ Which proves the statement since the base case is already proven.

This is by the way known as the Hockey-Stick Identity.

Answer 5

given that: $$\begin{pmatrix}a\\b\end{pmatrix}=^aC_b=\frac{a!}{b!(a-b)!}$$ you could try and re-write the summation this way as there will always be an $r!$ common term on the bottom, so try and write it all as one fraction and see where this goes