Next: Catalan numbers
Up: Generating Functions
Previous: First method
Or we can form an ordinary generating function
Then using the recurrence for and initial conditions we get
. 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
, a ``formal
power series''. It is deduced from the recurrence and the initial
Addition, subtraction, scalar multiplication, differentiation and
integration work as expected. The new thing is the ``product'' of
two such series:
is the ``convolution'' of the sequences
. 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.