Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to derive formula for generating function $$\sum_{n=0}^{+\infty}{m+n\choose m}z^n$$ because it is very often very useful for me. Unfortunately I'm stuck:

$$ f(z)=\sum_{n\ge 0}{m+n\choose n}z^n= \\ \sum_{n\ge 1}{m+n-1\choose n-1}z^n+\sum_{n\ge 0}{m+n-1\choose n}z^n= \\ zf(z)+\sum_{n\ge 0}{m+n-1\choose n}z^n$$

here, I'm afraid that there is a need for something more sophisticated than above trivial identity. Can you help me?

share|cite|improve this question
Isn't it just the binomial series? – EuYu Jul 30 '12 at 21:07
If I'm not crazy the GF of that is $$\frac{1}{(1-x)^m}$$ or something similar. Try to think about $(1-x)^{-m}$ and how to change $-m\choose n$ to something in terms of positive integers. – Pedro Tamaroff Jul 30 '12 at 21:09
GF of that is $$\frac{1}{(1-z)^{m+1}}$$ – ray Jul 30 '12 at 21:18
Yes, precisely. You're trying to prove that? – Pedro Tamaroff Jul 30 '12 at 21:18
No, I want to derive that, assuming that I don't know that. What typos? I can correct them, but don't see. – ray Jul 30 '12 at 21:20
up vote 4 down vote accepted

The function $\left(1 + z\right)^k$ has series expansion $$\left(1 + z\right)^k = \sum_{n\ge0}\binom{k}{n}z^n$$ We also have the binomial coefficient identity $$\binom{n}{k} = (-1)^k\binom{-n + k - 1}{k}$$ which together gives $$\sum_{n\ge 0}\binom{m+n}{n}z^n = \sum_{n\ge 0}\binom{-m-1}{n}(-z)^n = \frac{1}{(1-z)^{m+1}}$$ which is your required generating function.

share|cite|improve this answer
Right! it seems so obvious now. I'm sorry I had to ask, I should sleep more often maybe. Thank you so much. – ray Jul 30 '12 at 21:24


And obviously $f_0(z)=\frac{1}{1-z}$, so $f_m(z)=\frac{1}{(1-z)^{m+1}}$

share|cite|improve this answer
very nice too! I also tried this way and introduced $f_m(z)$ notation but I'm ashamed now, I didn't see that $f_0(z)=\frac{1}{1-z}$ so I thought that the solution isn't explicit. – ray Jul 30 '12 at 21:41

Your Answer


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.