0

I'm just trying to understand how ordinary generating functions works.. For example, how can I get the sequence of this OGF:

$F(z) = \frac{z^{2}}{(1-z)^3}$

I organized it as follows:

$F(z)=\frac{z^{2}}{(1-z)^3}=z^2\left ( \frac{1}{(1-z)^3} \right )=z^2\left ( \frac{1}{(1-z)}\frac{1}{(1-z)}\frac{1}{(1-z)} \right)$

because I know the sequence of $\frac{1}{1-z}$, witch is $1, 1, 1, ..., 1, ...$

However, I'm not seeing a way to develop this any further and find a sequence.

For example, I know if $\frac{1}{(1-z)}\frac{1}{(1-z)}\frac{1}{(1-z)}$ generates the sequence $a_0, a_1, ..., a_n, ...$, when I multiply it by $z^2$ I will get the sequence $0, 0, a_0, a_1, ..., a_n, ...$, but I have no idea how to obtain the values for $a_0, a_1, ..., a_n$

Eduardo Castilho
  • 89

1 Answers1

0

Since $$F(z)=\sum_{n\ge0}a_nz^n=\frac{z^2}{(1-z)^3}$$ the idea is then to extract $a_n$ from the power series expansion of $\frac{z^2}{(1-z)^3}$.

One way to do it is to compute the first few derivatives and compare their values at $z=0$ to the coefficients of the corresponding Taylor series centered at $z=0$:

$$F(z)=\sum_{n\ge0}\frac{F^{(n)}(0)}{n!}z^n$$

We have

$$\begin{align*} F(z)=\frac{z^2}{(1-z)^3}&\implies F(0)=0\implies a_0=0\\[1ex] F'(z)=\frac{z^2+2z}{(1-z)^4}&\implies F'(0)=0\implies a_1=0\\[1ex] F''(z)=\frac{2z^2+8z+2}{(1-z)^5}&\implies F''(0)=2\implies a_2=1 \end{align*}$$

and so on.

Another method would be to manipulate (mainly via differentiation) the well-known geometric series,

$$\sum_{n\ge0}z^n=\frac1{1-z}$$

until it matches $F(z)$. This is easy to do if you first decompose $F(z)$ into partial fractions:

$$\frac{z^2}{(1-z)^3}=\frac1{1-z}-\frac2{(1-z)^2}+\frac1{(1-z)^3}$$

Then noticing that

$$\frac{\mathrm d}{\mathrm dz}\left[\frac1{1-z}\right]=\frac1{(1-z)^2}=\sum_{n\ge0}(n+1)z^n$$

$$\frac{\mathrm d^2}{\mathrm dz^2}\left[\frac1{1-z}\right]=\frac2{(1-z)^3}=\sum_{n\ge0}(n+1)(n+2)z^n$$

we find

$$F(z)=\sum_{n\ge0}\left(1-2(n+1)+\frac{(n+1)(n+2)}2\right)z^n=\sum_{n\ge0}\frac{n(n-1)}2z^n$$

$$\implies\{a_n\}_{n\ge0}=\{0,0,1,3,6,10,15,\ldots\}$$

user170231
  • 19,334