Proving that $\sum\limits_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$ [duplicate]

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.

With minor modification, your opening up procedure will work. Write the Pascal Identity in the non-traditional order $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. (We have just reversed the addition order of your two terms.)

Now we do your computation, for clarity with $m+n+1=17$ and $m+1=5$. We get $$\binom{17}{5}=\binom{16}{4}+\binom{16}{5}=\binom{16}{4}+\binom{15}{4}+\binom{15}{5}.$$

Now decompose $\dbinom{15}{5}$ as $\dbinom{14}{4}+\dbinom{14}{5}$, and then $\dbinom{14}{5}$ as $\dbinom{13}{4}+\dbinom{13}{5}$, and so on.

If you want to be formal, you can easily write it up as an induction on $n$.

$${m+i+1\choose m+1}={m+i\choose m+1}+{m+i\choose m} $$ $$\Rightarrow $$ $${m+i\choose m}={m+i+1\choose m+1}-{m+i\choose m+1}$$

$$\text{let} \ i=1,2,...n$$

$${m+1\choose m}={m+1+1\choose m+1}-{m+1\choose m+1}$$

$${m+i\choose m}={m+i+1\choose m+1}-{m+i\choose m+1}$$

$${m+n\choose m}={m+n+1\choose m+1}-{m+n\choose m+1}$$

Add all the terms and we have following identities

$$\sum_1^n{m+i\choose m}={m+n+1\choose m+1}-{m+1\choose m+1}$$

And we know

$${m+1\choose m+1}={m\choose m}$$

So

$$\sum_0^n{m+i\choose m}={m+n+1\choose m+1}$$