TITLE: Prove the identity $\sum^{n}_{k=0}\binom{m+k}{k} = \binom{n+m+1}{n}$
QUESTION [1 upvotes]: Let $n,m \in \mathbb{N}$. Prove the identity $$\sum^{n}_{k=0}\binom{m+k}{k} = \binom{n+m+1}{n}$$

This seems very similar to Vandermonde identity, which states that for nonnegative integers we have $\sum^{m}_{k=0}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$. But, clearly this identity is somehow different from it. Any ideas?

REPLY [0 votes]: Using the Gosper's algorithm in Maxima:

AntiDifference(binomial(m+k,k),k);

$$
\binom{m+k}{k} =
(k+1)\frac{\binom{m+k+1}{k+1}}{m+1} - k\frac{\binom{m+k}{k}}{m+1}
$$
and the sum telescopes.
{"set_name": "stack_exchange", "score": 1, "question_id": 1521147}