# 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?

-
– barto Jun 25 at 20:17

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.

-

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Assuming $\ds{M \geq 0}$:

$$\mbox{Note that}\quad \sum_{m = 0}^{M}{m + k \choose k} = \sum_{m = k}^{M + k}{m \choose k} = a_{M + k} - a_{k - 1}\quad\mbox{where}\quad a_{n} \equiv \sum_{m = 0}^{n}{m \choose k}\tag{1}$$

Then, \begin{align} \color{#f00}{a_{n}} & \equiv \sum_{m = 0}^{n}{m \choose k} = \sum_{m = 0}^{n}\ \overbrace{% \oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{m \choose k}}\ =\ \oint_{\verts{z} = 1}{1 \over z^{k + 1}}\sum_{m = 0}^{n}\pars{1 + z}^{m} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1}{1 \over z^{k + 1}}\, {\pars{1 + z}^{n + 1} - 1 \over \pars{1 + z} - 1}\,{\dd z \over 2\pi\ic}\ =\ \underbrace{\oint_{\verts{z} = 1}{\pars{1 + z}^{n + 1} \over z^{k + 2}} \,{\dd z \over 2\pi\ic}}_{\ds{n + 1 \choose k + 1}}\ -\ \underbrace{\oint_{\verts{z} = 1}{1 \over z^{k + 2}}\,{\dd z \over 2\pi\ic}} _{\ds{\delta_{k + 2,1}}} \\[8mm] \imp\ \color{#f00}{a_{n}} & = \fbox{$\ds{\quad% {n + 1 \choose k + 1} - \delta_{k,-1}\quad}$} \end{align}
\begin{align} \mbox{With}\ \pars{1}\,,\quad \color{#f00}{\sum_{m = 0}^{M}{m + k \choose k}} & = \bracks{{M + k + 1 \choose k + 1} - \delta_{k,-1}} - \bracks{{k \choose k + 1} - \delta_{k,-1}} \\[3mm] & = {M + k + 1 \choose k + 1} - {k \choose k + 1} \end{align} Thanks to $\ds{@robjohn}$ user who pointed out the following feature: $${k \choose k + 1} = {-k + k + 1 - 1 \choose k + 1}\pars{-1}^{k + 1} = -\pars{-1}^{k}{0 \choose k + 1} = \delta_{k,-1}$$ such that $$\begin{array}{|c|}\hline\mbox{}\\ \ds{\quad\color{#f00}{\sum_{m = 0}^{M}{m + k \choose k}} = \color{#f00}{{M + k + 1 \choose k + 1} - \delta_{k,-1}}\quad} \\ \mbox{}\\ \hline \end{array}$$

-
Since $k=-1$ is covered in the first part, it should be noted that since $\binom{-1}{0}=1$, $$\binom{k}{k+1}-\delta_{k,-1}=0$$ therefore the final answer seems it should be $$\binom{M+k+1}{k+1}-\delta_{k,-1}$$ – robjohn yesterday
@robjohn Thanks. I'm checking everything right now. – Felix Marin yesterday
@robjohn Thanks. Fixed. – Felix Marin yesterday