combinatorics - Proving that $sumlimits_{k=0}^{n} {{m+k} choose{m}} = { m+n+1 choose m+1 }$

I have to prove that:

$$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$

I tried to open up the right side with Pascal's definition that:
$${ n \choose k} = {n-1 \choose {k}} + {n-1 \choose {k-1}}$$

Here is what I came up with, and I am sure it is wrong because it does not equal the left side:

$${m+n+1 \choose m+1} = {m+n \choose m+1} + {m+n \choose m} = ... ={m+n \choose m+1} + {m+n-1 \choose m} + {m+n-2 \choose m-1} + ... + {m \choose m+1} = \sum_{k=0}^{n} {m+k \choose m+k-n+1 }$$

Which, again, probably is wrong because it is not equal $\sum_{k=0}^{n} { m+k \choose m}$.
Any help is appreciated

Answer

Here is a purely combinatorial proof:

Consider picking $m+1$ numbers out of $\{1,2,...,m, \color{ #009900}{m + 1}, \color{ #009900}{m + 1} + 1,...,\color{ #009900}{m + 1} + (n - 1),\color{ #009900}{m + 1}+n\}$.

The right hand side of your equation is clearly equal to the number of ways of doing this.

Now for any given choice of $m+1$ numbers, the highest number chosen must be some $k$ with $\color{ #009900}{m + 1} \leq k \leq \color{ #009900}{m + 1}+n$. In each of these cases, we must select the remaining $m$ numbers to be chosen from the $k-1$ numbers smaller than $k$.

For $k = m +1$, must pick $m$ numbers to the left of $m + 1$, out of $\{\color{ #0073CF}{1, 2, ..., m}, m+1\}$.
Since there are $\color{#0073CF}{m}$ such numbers, so $\color{#0073CF}{m}$ possible choices for $m$.
Thus the total number of choices for $m$ numbers $= \binom{\color{#0073CF}{m}}{m}$.

For $k = m +2$, must pick $m$ numbers to the left of $m + 2$, out of $\{\color{ #0073CF}{1, 2, ..., m, m +1}, m+2\}$.
Since there are $\color{#0073CF}{m + 1}$ such numbers, so $\color{#0073CF}{m + 1}$ possible choices for $m$.
Thus the total number of choices for $m$ numbers $= \binom{\color{#0073CF}{m + 1}}{m}$.

...
For $k = m + 1 + n$, must pick $m$ numbers to the left of $m + 1 + n$, out of $\{\color{ #0073CF}{1, 2, ..., m, m +1, ..., m + n}, m+ n + 1\}$.
Since there are $\color{#0073CF}{m + n}$ such numbers, so $\color{#0073CF}{m + n}$ possible choices for $m$.
Thus the total number of choices for $m$ numbers $= \binom{\color{#0073CF}{m + n}}{m}$.

Summing up the number of ways of doing this for $k=m+1,...,m+n+1$ yields the LHS of your equation.