Generating Functions
Table of Contents

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License