# Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

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?

-

Recall that for $k\in\Bbb N$ we have the generating function

$$\sum_{n\ge 0}\binom{n+k}kx^n=\frac1{(1-x)^{k+1}}\;.$$

The identity in the question can therefore be rewritten as

$$\left(\sum_{n\ge 0}\binom{n+k}kx^n\right)\left(\sum_{n\ge 0}x^n\right)=\sum_{n\ge 0}\binom{n+k+1}{k+1}x^n\;.$$

The coefficient of $x^n$ in the product on the left is

$$\sum_{i=0}^n\binom{i+k}k\cdot1=\sum_{i=0}^n\binom{i+k}k\;,$$

and the $n$-th term of the discrete convolution of the sequences $\left\langle\binom{n+k}k:n\in\Bbb N\right\rangle$ and $\langle 1,1,1,\dots\rangle$. And at this point you’re practically done.

-
Is there a typo in the second equation (first sum)? I believe $k$ should be indexed. –  AlanH May 27 '13 at 6:20
@Alan: No, the sum is over $n$; $k$ is fixed throughout. –  Brian M. Scott May 27 '13 at 7:19
In my text, I have an identity $\sum_{r\geq 0} \binom{r + n}{r} x^r = 1/(1-x)^{n+1}$ This may be the cause of my confusion, but is this identity correct and is it equivalent to the one you used? –  AlanH May 27 '13 at 8:22
@Alan: Sure: your $r$ is my $n$, and your $n$ is my $k$. –  Brian M. Scott May 27 '13 at 8:28
@Alan: $\binom{r+n}r=\binom{r+n}n$; now do the translation. (Sorry: I didn’t notice before that you’d used the symmetrically opposite binomial coefficient.) –  Brian M. Scott May 27 '13 at 19:19

You remember that: $$(1+x)^m = \sum_k \binom{m}{k} x^k$$ So the sum $$\sum_{m=0}^M \binom{m+k}{k}$$ is the coefficient of $x^k$ in: $$\sum_{m=0}^M (1+x)^{m+k}$$ Yes? So now use the geometric series formula given: $$\sum_{m=0}^M (1+x)^{m+k} = -\frac{(1+x)^k}{x} \left( 1 - (1+x)^{M+1} \right)$$ And now you want to know what is coefficient of $x^k$ in there. You got it from here.

-

In this answer, I prove the identity $$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}\tag{1}$$ Here is a generalization of the identity in question, proven using the Vandermonde Identity \begin{align} \sum_{m=0}^M\binom{m+k}{k}\binom{M-m}{n} &=\sum_{m=0}^M\binom{m+k}{m}\binom{M-m}{M-m-n}\tag{2}\\ &=\sum_{m=0}^M(-1)^m\binom{-k-1}{m}(-1)^{M-m-n}\binom{-n-1}{M-m-n}\tag{3}\\ &=(-1)^{M-n}\sum_{m=0}^M\binom{-k-1}{m}\binom{-n-1}{M-m-n}\tag{4}\\ &=(-1)^{M-n}\binom{-k-n-2}{M-n}\tag{5}\\ &=\binom{M+k+1}{M-n}\tag{6}\\ &=\binom{M+k+1}{n+k+1}\tag{7} \end{align} Explanation:
$(2)$: $\binom{n}{k}=\binom{n}{n-k}$
$(3)$: apply $(1)$ to each binomial coefficient
$(4)$: combine the powers of $-1$ which can then be pulled out front
$(5)$: apply Vandermonde
$(6)$: apply $(1)$
$(7)$: $\binom{n}{k}=\binom{n}{n-k}$

To get the identity in the question, set $n=0$.

-
@FoF: I have added a link here and answered your other question. Thanks for mentioning the difficulty. –  robjohn Dec 7 '13 at 12:33
@FoF: That is the Vandermonde Identity that I mentioned at the beginning. –  robjohn Dec 8 '13 at 18:56
@FoF: I added an explanation for each line. –  robjohn Dec 9 '13 at 2:20
I answered my own question about $(5, 6$) here. –  NaN Dec 10 '13 at 8:54
@FoF: Ah. That is why I added the Explanation when I saw difficulty in following the argument. –  robjohn Dec 11 '13 at 7:46

A standard technique to prove such identities $\sum_{i=0}^Mf(i)=F(M)$, involving on one hand a sum where only the upper bound $M$ is variable and on the other hand an explicit expression in terms of$~M$, is to use induction on$~M$. It amounts to showing that $f(M)=F(M)-F(M-1)$ (and that $F(0)=f(0)$). This is similar to using the fundamental theorem of calculus in showing that $\int_0^{x_0}f(x)\mathrm dx=F(x_0)$ by establishing $f(x)=F'(x)$ (and $F(0)=0$).

So here you need to check (apart from the obvious starting case $M=0$) that $\binom{M+k}k=\binom{M+k+1}{k+1}-\binom{M+k}{k+1}$. This is just in instance of Pascal's recurrence for binomial coefficients.

-