prove that $ \binom{n-1}{0} +\binom{n}{1}+\binom{n+1}{2}+\cdots+\binom{n+k}{k+1}=\binom{n+k+1}{k+1}$ I am asked to prove that $$ \dbinom{n-1}{0} +\dbinom{n}{1}+\dbinom{n+1}{2}+\cdots+\dbinom{n+k}{k+1}=\dbinom{n+k+1}{k+1}$$
So far what I've tried ,without looking to much at the sum I've to prove ,is that if I have $n+k+1$ blocks and I want to choose $k+1$ of them I can split $\dbinom{n+k+1}{k+1}$ in two major cases,namely $$\dbinom{n+k+1}{k+1}=\dbinom{n+k}{k+1} +\dbinom{n+k}{k}$$
This is equivalent to choose $k+1$ blocks of $n+k+1$ excluding a specific block $A$ ,$\dbinom{n+k}{k+1}$,and the other case is where I include the specific block $A$ ,$\dbinom{n+k}{k}$.
I've only matched one term,so I belive that the rest of the terms is just some identity applied to $\dbinom{n+k}{k}$ which I can't see ,or don't know, now.
Any help to put me in the right route is appreciated.
 A: LHS can be written as:
$$\binom{n-1}0+\left[\binom{n}1-\binom{n-1}0\right]+\cdots+\left[\binom{n+k+1}{k+1}-\binom{n+k}{k}\right]$$
"Telescoping" you find the RHS.
A: Suppose you have $n$ indistinguible balls and $k$ diferent boxes. The number of ways for distribute the $n$ balls in the $k$ boxes is $\binom{n+k-1}{k-1}$. 
On the other hand, we can first put $r$ balls in the first box, $r\in\{0,1,...,n\}$, and distribute the other $n-r$ in the $k-1$ boxes: $\binom{n-r+k-1-1}{k-2}=\binom{n-r+k-2}{k-2}$.
Since the two ways of distributed the balls are equivalents, then $\binom{n+k-1}{k-1}=\sum_{r=0}^n\binom{n-r+k-2}{k-2}$
Using it, it is easy to proof your assertion.
PD: The identity you try to prove is known as "Golf Stick Identity".
A: I think the left-hand side should have $k+2$ terms, not four:
$$\dbinom{n-1}{0} +\dbinom{n}{1}+\dbinom{n+1}{2}+\cdots+\dbinom{n+k}{k+1}=\dbinom{n+k+1}{k+1}$$
The rest of the terms after you subtract $n+k\choose k+1$ have the same form as the original equation, but with $k$ replaced by $k-1$.  So use induction on $k$.
