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

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

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:

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

which gives the required expression:

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

For the Perrin series, the similar procedure gives

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

- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs
- Matching Socks in Dark Room

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny64644396 |