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)Then the generating function for $(a_i)_{i=0}$ is:
(2)Notice that $F$ is merely the Maclaurin series for $e^x$, that is:
(3)For another example, fix $n \in \{0, 1, 2, ... \}$ and consider the finite sequence of binomial coefficients:
(4)The generating function for $(a_i)_{i=0}^{n}$ is:
(5)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)The generating function for this sequence is:
(7)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.