Why does generating functions work? (recurrence relations)

Question

I guess the title says it all. However, I have skimmed through several books, and while they all tell you how to use generating functions to find an expression for the n'th term of a recurrence relation, none of them say why it works.

I think I have a somewhat intuitive understanding of what is going on, but I think I need a more definitive explanation.

Answer 1

The generating function method works because it allows you to "handle" the recurrence formula for a sequence $(a_n)$. Indeed if we want to find a closed expression for a sequence $(a_n)$ from a recurrence formula it might be impossible to get the closed formula. Setting :

$$A(X)=\sum_na_nX^n $$

We are able to "translate" the recurrence formula for $(a_n)$ into a nice equation on $A(X)$ (the equation could be polynomial, differential, functional...).

When we do this we strongly believe that we will get an equation, and that this equation will be solvable. Finally we need a good library of generating function to make sure that our solution has explicit coefficients.

To answer your question, using generating function with a sequence $(a_n)$ verifying a recurrence formula is a way to consider the sequence $(a_n)$ as an object and then the recurrence formula is not considered on each $a_n$ anymore but is rather a property that the object $(a_n)$ verifies. Doing this we apply the recurrence formula to each $a_n$ at the same time, there is no doubt that applying the recurrence formula to each $a_n$ we will get more information than applying it to one $a_n$ at the time.

A good reference for this is the book from Herbert S Wilf : $\underline{\text{generatingfunctionology}}$. In it you will see that instead of considering ordinary generating functions :

$$\sum_na_nX^n$$

you could also use exponential generating functions :

$$\sum_n\frac{a_n}{n!}X^n $$

or arithmetic ones :

$$\sum_{n\geq 1}\frac{a_n}{n^s}$$

The generating function you need to use to study $(a_n)$ is strongly related to the recurrence formula it verifies. Hence we understand that the use of generating functions is not magical, when the recurrence formula simply involves lower terms of $a_k$ then we use ordinary generating functions (e.g. Catalan numbers), when it uses lower terms of $a_k$ and $\begin{pmatrix}n\\k\end{pmatrix}$ one should use exponential ones (e.g. Bell numbers) and when it involves a sum over the divisors of $n$ then one should use arithmetic generating functions (e.g. Moebius inversion).

Answer 2

It's because you always use a analytic function that is the generating function. In addition the operations you do is such that you always retain (uniform) convergence on a disc so you can also do the operations termwise.

This will make sure that the Taylor series will correspond to the intended series.

This would imply that you couldn't rely on generating series if the sequence grows so fast that it wouldn't allow for convergence of the series at all.

As pointed out by Brian M. Scott it's not required that the series actually converges, but in those case it's a bit of misnomer to call the generating functions for functions (since they only converge for $z=0$ and therefore as function are not that interresting). In that case you'll have to treat them as just being formal infinite sums (compare to polynomial rings) and have to treat them (somewhat) differently from functions.