It's said that the generating function for $g(x) = \sum_{d=0}^\infty {d+m-1 \choose m-1} x^d$ is equal to $\frac{1}{(1-x)^m}$.

In the proof that I have seen it states that:

By the geometric series, $\frac{1}{1-x} = 1+x+x^2+... = \sum_{d=0}^\infty {d \choose 0} x^d$

Differentiating gives $\frac{1}{(1-x)^2} = \sum_{d=0}^\infty {d \choose 1} x^d$

Differentiating again gives $\frac{1}{(1-x)^3} = \sum_{d=0}^\infty {d \choose 2} x^d$

And so on, but does this not show that the generating function is $g(x) = \sum_{d=0}^\infty {d \choose m-1} x^d$ or am I missing something?

  • $\begingroup$ $\sum_{0}^{\infty}$ is ambiguous. You probably mean $\sum_{d=0}^{\infty}$ $\endgroup$ – Alex Apr 22 '16 at 12:56
  • $\begingroup$ $\binom{j}{k}$ for $j<k$ is 0 $\endgroup$ – Alex Apr 22 '16 at 12:57
  • $\begingroup$ Differentiating should give $$\frac{1}{(1-x)^2}=\sum_{d} \binom{d+1}{1}x^d$$ The +1 is very important. $\endgroup$ – Thomas Andrews Apr 22 '16 at 13:36

The first part requires a proof by induction that is merely hinted at in what you’ve written: if

$$\frac1{(1-x)^m}=\sum_{d\ge 0}\binom{d+m-1}{m-1}x^d\;,$$

differentiating yields

$$\begin{align*} \frac{m}{(1-x)^{m+1}}&=\sum_{d\ge 0}d\binom{d+m-1}{m-1}x^{d-1}\\ &=\sum_{d\ge 0}d\binom{d+m-1}dx^{d-1}\\ &=\sum_{d\ge 0}(d+m-1)\binom{d+m-2}{d-1}x^{d-1}\\ &=\sum_{d\ge 0}(d+m)\binom{d+m-1}dx^d\\ &=\sum_{d\ge 0}(d+m)\binom{d+m-1}{m-1}x^d\\ &=\sum_{d\ge 0}m\binom{d+m}mx^d\;. \end{align*}$$

Now just divide both sides by $m$ to get

$$\frac1{(1-x)^{m+1}}=\sum_{d\ge 0}\binom{d+m}mx^d\;.$$

You’re right that this doesn’t justify the $g(x)$ that you’ve written. In fact

$$\sum_{d\ge 0}\binom{d+m}mx^d=\sum_{d\ge 0}\binom{d}mx^{d-m}\;,$$

since $\binom{k}\ell=0$ if $k<\ell$, and therefore

$$\sum_{d\ge 0}\binom{d}mx^d=\frac{x^m}{(1-x)^{m+1}}\;.$$

| cite | improve this answer | |
  • $\begingroup$ Perfect, thank you so much! $\endgroup$ – user328251 Apr 22 '16 at 13:26
  • $\begingroup$ @user328251: You’re welcome! $\endgroup$ – Brian M. Scott Apr 22 '16 at 13:27

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.