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?

  • $\begingroup$ Isn't it just the binomial series? $\endgroup$ – EuYu Jul 30 '12 at 21:07
  • $\begingroup$ 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. $\endgroup$ – Pedro Tamaroff Jul 30 '12 at 21:09
  • $\begingroup$ GF of that is $$\frac{1}{(1-z)^{m+1}}$$ $\endgroup$ – ray Jul 30 '12 at 21:18
  • $\begingroup$ Yes, precisely. You're trying to prove that? $\endgroup$ – Pedro Tamaroff Jul 30 '12 at 21:18
  • $\begingroup$ No, I want to derive that, assuming that I don't know that. What typos? I can correct them, but don't see. $\endgroup$ – ray Jul 30 '12 at 21:20

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.

  • $\begingroup$ Right! it seems so obvious now. I'm sorry I had to ask, I should sleep more often maybe. Thank you so much. $\endgroup$ – 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}}$

  • $\begingroup$ 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. $\endgroup$ – ray Jul 30 '12 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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