# 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.