# Generating function for multiset formula

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?

• $\sum_{0}^{\infty}$ is ambiguous. You probably mean $\sum_{d=0}^{\infty}$ – Alex Apr 22 '16 at 12:56
• $\binom{j}{k}$ for $j<k$ is 0 – Alex Apr 22 '16 at 12:57
• Differentiating should give $$\frac{1}{(1-x)^2}=\sum_{d} \binom{d+1}{1}x^d$$ The +1 is very important. – 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}}\;.$$

• Perfect, thank you so much! – user328251 Apr 22 '16 at 13:26
• @user328251: You’re welcome! – Brian M. Scott Apr 22 '16 at 13:27