Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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.

share|improve this answer

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$.

share|improve this answer
2  
@FoF: I have added a link here and answered your other question. Thanks for mentioning the difficulty. –  robjohn Dec 7 '13 at 12:33
1  
@FoF: That is the Vandermonde Identity that I mentioned at the beginning. –  robjohn Dec 8 '13 at 18:56
1  
@FoF: I added an explanation for each line. –  robjohn Dec 9 '13 at 2:20
1  
I answered my own question about $(5, 6$) here. –  NaN Dec 10 '13 at 8:54
1  
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.