Next: Catalan numbers Up: Generating Functions Previous: First method   Contents

### Second Method

Or we can form an ordinary generating function

Then using the recurrence for and initial conditions we get that . We wish to find the coefficient of in the expansion of (which is denoted ). 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 is , 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:

where

is the convolution'' of the sequences and . 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