algebra precalculus - Simplify the expression $binom{n}{0}+binom{n+1}{1}+binom{n+2}{2}+cdots +binom{n+k}{k}$

Simplify the expression $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k}{k}$

My attempt: Using the formula $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$

$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots \binom{n+k-1}{k-1}+\binom{n+k}{k}$

=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k-1}{k-1}+(\binom{n+k-1}{k}+\binom{n+k-1}{k-1})$

=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +2\binom{n+k-1}{k-1}+\binom{n+k-1}{k}$

I can again use the same formula for the term $2\binom{n+k-1}{k-1}$, and in the next to step to the term $3\binom{n+k-2}{k-2}$.

But I don't think this way the expression will get simplified.

Any help is appreciated.

Answer

First show that $\large{n\choose r}={{n-1}\choose {r-1}}+{{n-1}\choose r}$,

from which we get $\large{{n+r+1}\choose r}={{n+r}\choose r}+{{n+r}\choose {r-1}}$

By the same rule, $\large{{n+r}\choose {r-1}}={{n+r-1}\choose {r-1}}+{{n+r-1}\choose {r-2}}$

$\large{{n+r-1}\choose {r-2}}={{n+r-2}\choose {r-2}}+{{n+r-3}\choose {r-3}}$

$..$ $\quad \quad \quad \quad ..$ $\quad \quad \quad ..$

$..$ $\quad \quad \quad \quad ..$ $\quad \quad \quad ..$

$..$ $\quad \quad \quad \quad ..$ $\quad \quad \quad ..$

$\large{{n+3}\choose {2}}={{n+2}\choose {2}}+{{n+2}\choose {1}}$

$\large{{n+2}\choose {1}}={{n+1}\choose {1}}+{{n+1}\choose {0}}$

Adding, we get $\large{n\choose 0}+{{n+1}\choose 1}+...+{{n+r-1}\choose {r-1}}+{{n+r}\choose r}={{n+r+1}\choose r}$

---

Alternatively, we can fix any $r$ of the $(n+r+1)$ objects given. Label them $A_1,A_2,...A_r$. Now our choices of $r$ objects from the $(n+r+1)$ objects may or may not contain any or all of the set $\{A_1,A_2,...,A_r\}$.

Case I: It does not contain $A_1$

This will happen in $\large{{n+r}\choose r}$ ways as the $r$ things have to be chosen from the remaining $(n+r)$ things.

Case II: It contains $A_1$ but does not contain $A_2$.

This will happen in $\large{{n+r-1}\choose {r-1}}$ ways, because having chosen $A_1$ and rejectd $A_2$, we have only $(n+r-1)$ things to choose from and we need only $(r-1)$.

$...$

Case r: It contains $A_1,A_2,...,A_{r-1}$ but does not contain $A_r$.

This will happen in $\large {{n+1}\choose 1}$ ways.

Case $(r+1)$: It contains $A_1,A_2,...,A_r$.

This will happen in $\large{n\choose 0}=1$ way.

Hence, $\displaystyle\sum_{k=0}^{r}{{n+k}\choose k}={{n+r+1}\choose r}$