# Prove $\sum_{k=0}^n \binom{m+k}{m} = \binom{m+n+1}{m+1}$ using the binomium of Newton

Prove $$\sum_{k=0}^n \binom{m+k}{m} = \binom{m+n+1}{m+1}$$ by considering the coefficient of $$x^n$$ in $$(1-x)^{-1} (1-x)^{-m-1} = (1-x)^{-m-2}$$.

I have succeeded in proving this using induction and in a combinatorial way, but I need to practice with power series.

Background: third year mathematics at university

My attempt

The given equality can be rewritten as

$$\left( \sum_{k=0}^\infty \binom{-1} k (-x)^k \right) \left( \sum_{\ell=0}^\infty \binom{-m-1}{\ell} (-x)^\ell \right) = \sum_{n=0}^\infty \binom{-m-2}{n} x^n (-1)^n$$

and we can work out the left-hand side as

$$\sum_{n=0}^\infty \sum_{k+\ell=n} \binom{-1}{k} \binom{-m-1}{\ell} (-x)^{k+\ell} = \sum_{n=0}^\infty \sum_{k=0}^n \binom{-1}{k} \binom{-m-1}{n-k} x^n (-1)^n$$

and now we equate the coefficients in front of $$x^n$$ on both sides to get

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

But how to proceed? Because I don't see the original equation in this.

• Hockey Stick Identity – Yadati Kiran Dec 19 '18 at 8:20
• @YadatiKiran Thanks for the link, it is indeed the same! Now to figure out from the many answers how to prove it using power series. – PHPirate Dec 19 '18 at 8:52
• Ok maybe it is not quite the same, there are ideas in those answers similar to mine but the problem here remains. – PHPirate Dec 19 '18 at 9:10

I mean, you're pretty much done from where you got at. Just note that $${ -1 \choose k}=(-1)^k$$ and $${-m-2 \choose n}= {m+n+1 \choose n}$$(up to some minus sign) and $${-m-1 \choose k}={m+k \choose k}$$(use this instead of $${-m-1 \choose n-k}$$ on the LHS of your identity by just changing k to n-k). To prove these identities just write out your binomial coefficients in full.
• Indeed it almost works out, I have the LHS equal but for the RHS I have $\binom{-m-2}{n}=(-1)^n \binom{m+n+1}{n}$, so it is almost equal to $\binom{m+n+1}{m+1}$ except for the minus sign, which stays, right? – PHPirate Dec 19 '18 at 9:36
• For the LHS I have that they are exactly equal: $\binom{-1}{k} \binom{-m-1}{k} = (-1)^k (-1)^k \binom{m+k}{k}=\binom{m+k}{m}$ as you say, so that's not where the $(-1)^n$ disappears. – PHPirate Dec 19 '18 at 9:40
• Oh I see, I have a $(-1)^n$ wrong in my attempt in the question! Thanks! – PHPirate Dec 19 '18 at 9:45