Generating Functions

# Generating Functions

On the A Closed Form of the Fibonacci Sequence page we found a closed form for generating the sequence of Fibonacci numbers $\{ f_n \}$. In finding this closed form, we generated the function $F(x) = f_1 + f_2x + f_3x^2 + ... + f_nx^{n-1} + f_{n+1}x^n + ...$ and algebraically manipulated it. We will see that the procedure done can be used for other sequences.

 Definition: If $(a_i)_{i=0}^{\infty} = \{ a_0, a_1, a_2, ... \}$ is a sequence of real numbers then the Generating Function of $(a_i)_{i=0}^{\infty}$ is $F(x) = a_0 + a_1x + a_2x^2 + ... + a_ix^i + ... = \sum_{i=0}^{\infty} a_ix^i$.

A generating function can also be defined for a finite sequence. If $(a_i)_{i=0}^{n}$ is a finite sequence then by extending the sequence to the infinite sequence $(b_i)_{i=0}^{\infty}$ where $b_i = \left\{\begin{matrix} a_i & \mathrm{if \: 0 \leq i \leq n}\\ 0 & \mathrm{if \: i > n} \end{matrix}\right.$, i.e, $(b_i)_{i=0}^{\infty} = \{ a_0, a_1, a_2, ..., a_n, 0, 0, ...)$. Then the generating function of $(a_i)_{i=0}^{n}$ is defined to be the generating function of $(b_i)_{i=0}^{\infty}$ which is simply $F(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n = \sum_{i=0}^{n} a_ix^i$.

In particular, if we are given a generating function $F(x) = a_0 + a_1x + a_2x_2 + ... + a_nx^n + ...$ then the coefficient in front of $x^i$ for $i \in \{0, 1, 2, ... n \}$ is the term $a_i$ in the sequence $(a_i)_{i=0}^{\infty}$.

For example, consider the following sequence:

(1)
\begin{align} \quad (a_i)_{i=0}^{n} = \left ( \frac{1}{i!} \right)_{i=0}^{n} = \{ \frac{1}{0!}, \frac{1}{1!}, \frac{1}{2!}, \frac{1}{3!}, ... \end{align}

Then the generating function for $(a_i)_{i=0}$ is:

(2)
\begin{align} \quad F(x) = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ... + \frac{x^n}{n!} + ... = \sum_{i=0}^{\infty} \frac{x^i}{i!} \end{align}

Notice that $F$ is merely the Maclaurin series for $e^x$, that is:

(3)
\begin{align} \quad e^x = \sum_{i=0}^{\infty} \frac{x^i}{i!} \end{align}

For another example, fix $n \in \{0, 1, 2, ... \}$ and consider the finite sequence of binomial coefficients:

(4)
\begin{align} \quad (a_i)_{i=0}^{n} = \left ( \binom{n}{i} \right)_{i=0}^{n} = \left \{ \binom{n}{0}, \binom{n}{1}, ..., \binom{n}{n-1}, \binom{n}{n} \right \} \end{align}

The generating function for $(a_i)_{i=0}^{n}$ is:

(5)
\begin{align} \quad F(x) = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + ... + \binom{n}{n-1}x^{n-1} + \binom{n}{n}x^n = \sum_{i=0}^{n} \binom{n}{i}x^i \end{align}

We know by The Binomial Theorem that the finite sum above is the binomial expansion of the binomial $(1 + x)^n$, i.e., $F(x) = (1 + x)^n$.

So why exactly are generating functions useful? Well, let's put this question in the context of an example. For $n$ people suppose that we want to choose $3$ of them. We know that the number of ways this can be done is $\binom{n}{3}$. Now consider the sequence corresponding to this problem:

(6)
\begin{align} \quad \left ( \binom{n}{0}, \binom{n}{1}, \binom{n}{2}, ..., \binom{n}{n} \right ) \end{align}

The generating function for this sequence is:

(7)
\begin{align} \quad F(x) = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + ... + \binom{n}{n} x^n \end{align}

Notice that the coefficient $a_3 = \binom{n}{3}$ of our generating function $F$ also tells us the number of ways this can be done. In fact, each coefficient gives of $F$ gives us a solution to a related problem. For more complicated problems, we may not have a sequence $(a_i)_{i=0}^{\infty}$ to even start with. We may only have a description of what our sequence describes. In such cases, we will want to obtain a generating function $F$ as $F$ will have all of the "encoded" information of the described generating sequence. We then find the coefficient $a_n$ of the term $x^n$ of our generating function which pertains to the solutions to the problem we pose.

We will discuss more into generating functions on the More on Generating Functions page.