Generating Functions from Recurrences

A generating function for a sequence \(\{x_n\}\) is a formally defined power series \(\sum a_{n}x^{n}\). It is often the case that the sequence \(\{x_n\}\) is defined recursively via a recurrence relation. This is, for example, true for the Fibonacci sequence \(0, 1, 1, 2, 3, \ldots\), where

\(F_n= \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1}+F_{n-2} & \mbox{if } n > 1, \\ \end{cases} \)

or for the Perrin sequence \(3, 0, 2, 3, 2, 5, 5, 7, \ldots\) obtained via

\(P_n= \begin{cases} 3 & \mbox{if } n = 0; \\ 0 & \mbox{if } n = 1; \\ 2 & \mbox{if } n = 2; \\ P_{n-2}+P_{n-3} & \mbox{if } n > 2. \\ \end{cases} \)

The problem I want to discuss is how to obtain an expression for a generating function associated with a sequence defined recursively. As usual, I shall ignore the question of the convergence of the formal series. Let's simply look at a couple of examples. It's convenient to write \([x^n]a(x)=A_n\) for the coefficients in the series that define function \(a(x)=\sum_{n=0} A_{n}x^{n}\).

Let \(f(x)=\sum_{n=0} F_{n}x^{n}\), where the coefficients are the Fibonacci numbers defined above. From the definition and by changing the indexing,

\(xf(x)=x\sum_{n=0} F_{n}x^{n}=\sum_{n=0} F_{n}x^{n+1}=\sum_{n=1} F_{n-1}x^{n}\),

such that \([x^{n}]xf(x)=F_{n-1}\). Similarly,

\(x^{2}f(x)=x^{2}\sum_{n=0} F_{n}x^{n}=\sum_{n=0} F_{n}x^{n+2}=\sum_{n=2} F_{n-2}x^{n}\),

and \([x^{n}]x^{2}f(x)=F_{n-2}\). From the Fibonacci recurrence relation, for \(n\gt 1\), \([x^{n}](x+x^{2})f(x)=[x^{n}]f(x)\). To see how can we account for the initial conditions, \(F_{0}=0\) and \(F_{1}=1\) I shall write the three series explicitly:

\( \begin{align} f(x) &= F_{0} +& F_{1}x +& F_{2}x^{2} +& F_{3}x^{3} +&\ldots\\ xf(x) &= & F_{0}x +& F_{1}x^{2} +& F_{2}x^{3} +&\ldots\\ x^{2}f(x) &= & & F_{0}x^{2} +& F_{1}x^{3} +&\ldots\\ \end{align} \)

Due to the Fibonacci recurrence relation, if we subtract the last two equations from the first one, we'll obtain

\((1-x-x^{2})f(x)=F_{0}+(F_{1}-F_{0})x=x\),

which gives the required expression:

\(f(x)=\frac{x}{1-x-x^{2}}\).

(Elswhere, we use this generating function to derive Binet's formula for the Fibonacci numbers.)

For the Perrin series, the similar procedure gives

\(p(x)=\frac{3-x^{2}}{1-x^{2}-x^{3}}\).

As I hope is clear, every recurrence relation can be folded into a closed form function that embodies information about the entire series. As we shall see later, such representations prove rather useful for the study of the series.

Generating Functions

71867889