Generating function for multiset formula

1k Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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}}\;.$$