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.

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|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
add comment

2 Answers

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|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
add comment

$$f_m(z).(1-z)=\sum\left(\binom{m+n}{n}-\binom{m+n-1}{n-1}\right)z^n=\sum\binom{(m-1)+n}{n}z^n=f_{m-1}(z)$$

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

share|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
add comment

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.