<s>[INST] 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.
 [/INST] 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}$
</s>