next up previous contents
Next: Catalan numbers Up: Generating Functions Previous: First method   Contents

Second Method

Or we can form an ordinary generating function

$\displaystyle G(z) = \sum_{n \ge 0} F_n z^n.

Then using the recurrence for $ F_n$ and initial conditions we get that $ G(z) (1 - z - z^2) = z$. We wish to find the coefficient of $ z^n$ in the expansion of $ G(z)$ (which is denoted $ [z^n]G(z)$). We use partial fractions and the binomial expansion to obtain the same result as before. In general, the ordinary generating function associated with the sequence $ (a_n)_{n \in \mathbb{N}_0}$ is $ G(z) = \sum_{n \ge 0} a_n z^n$, a ``formal power series''. It is deduced from the recurrence and the initial conditions. Addition, subtraction, scalar multiplication, differentiation and integration work as expected. The new thing is the ``product'' of two such series:

$\displaystyle \sum_{k \ge 0} a_k z^k \sum_{l \ge 0} b_l z^l
= \sum_{n \ge 0} c_n z^n,$   where $\displaystyle c_n = \sum_{k=0}^n a_k b_{n-k}.

$ (c_n)_{n \in \mathbb{N}_0}$ is the ``convolution'' of the sequences $ (a_n)_{n \in \mathbb{N}_0}$ and $ (b_n)_{n \in \mathbb{N}_0}$. Some functional substitution also works. Any identities give information about the coefficients. We are not concered about convergence, but within the radius of convergence we get extra information about values.

root 2002-06-10