Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$

I recognize the identity that they give from generating functions, but how does that help prove the identity?

Can someone provide a hint as to how to approach this problem?


merged by Jack D'Aurizio Dec 12 '17 at 6:28

This question was merged with Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$ because it is an exact duplicate of that question.