Generating Fucntion Tutorial

Let's begin with a very famous sequence: \(0\ 1\ 1\ 2\ 3\ 5\ 8\ 13\ 21\ 34\ 55\ 89\ 144\) . They are Fibonacci numbers, which can be defined as:

(1)
\[\begin{align} \def\phihat{\rlap{\phi}{\phantom{\hspace{0.4ex}}\widehat{\phantom{\varphi}}}} \def\phihats{\rlap{\phi}{\phantom{\hspace{0.1ex}}\widehat{\phantom{\varphi}}}} \def\phia{\phi} \def\phib{\varphi} \def\phic{\phib} F_{n}=\begin{cases} 0 & n=0\\ 1 & n=1\\ F_{n-1}+F_{n-2} & n>1 \end{cases} \end{align}\]

This is a recursive definition, which is good, but it's not straightforward enough. For example, if we want to know \(F_{100}\), we'll have to calculate \(F_{0}\), \(F_{1}\), \(\ldots\), \(F_{98}\) and \(F_{99}\). This is a lot of math to do. Is there any better solution? Or, is there a closed form for Fibonacci numbers?

Fortunately the answer is yes, and (unsurprisingly) generating function is such a tool to solve such kinda recurrence.

Generating function is smart and subtle. The only way to understand it is to see how it works by an example. Here in this tutorial, I'll show you how generating function solves Fibonacci numbers recurrence.

Generally speaking, four steps are needed to solve a recurrence via generating function:

  1. Write down a single equation that expresses \(g_{n}\) in terms of other elements of the sequence (assuming that \(g_{-1}=g_{-2}=\cdots=0\)).
  2. Multiply both sides of the equation by \(z^{n}\) and sum over all \(n\). This gives, on the left, the sum \(G(z)=\sum_{n}g_{n}z^{n}\), which is the generating function \(G(z)\). The right-hand side should be manipulated so that it becomes some other expression involving \(G(z)\).
  3. Solve the resulting equation, getting a closed form for \(G(z)\).
  4. Expand \(G(z)\) into a power series and read off the coefficient of \(z^n\); this is a closed form for \(g_n\).

Let's apply these steps to Fibonacci numbers.

Step 1

At the beginning of this tutorial, we have seen the recursive definition of Fibonacci numbers (equation (1)), but it is not a single equation. So let's simplify it:

(2)
\[g_{n}=g_{n-1}+g_{n-2}+[n=1]\]

Note that:

  1. We use \(g_{n}\) instead of \(F_{n}\).
  2. \([n=1]\) is the trick to make a single equation, it is defined as \([n=m] = \begin{cases} 1 & n=m\\ 0 & n\neq m \end{cases}\:\), therefore \([n=1]\) equals \(1\) iff \(n=1\), which makes (2) hold for any \(n\ge 0\).

Step 2

Let's multiply both sides of equation (2) by \(z^{n}\):

\[g_{n}z^{n} = g_{n-1}z^{n} + g_{n-2}z^{n} + [n=1]z^{n}\]
\[\]

and sum over all \(n\):

\[\begin{align} G(z) = \sum_{n}g_{n}z^{n} &= \sum_{n}g_{n-1}z^{n} + \sum_{n}g_{n-2}z^{n} + \sum_{n}[n=1]z^{n} \\ &= n\sum_{n}g_{n-1}z^{n-1} + n^2\sum_{n}g_{n-2}z^{n-2} + z \\ &= n\sum_{n}g_{n}z^{n} + n^2\sum_{n}g_{n}z^{n} + z \\ &= zG(z)+z^{2}G(z)+z \end{align}\]
\[\]

Please keep in your mind that \(G(z)=\sum_{n}g_{n}z^{n}=g_0+g_1z+g_2z^2+\cdots\), that is to say, if we denote \(G(z)\) as a power series, then the coefficients of \(z^n\) will be \(F_n\).

Step 3

Solve the equation \(G(z)=zG(z)+z^{2}G(z)+z\), getting a closed form for \(G(z)\):

\[G(z)=\frac{z}{1-z-z^{2}}\]

Step 4

Here comes the hardest part: to expand \(G(z)\) into a power series. How can we do this? Well, there are more than one way to achieve it, but as to this Fibonacci question, there is a simple but smart way.

You may recall that

(3)
\[\frac{1}{1-\alpha z}=1+\alpha z+\alpha^2 z^2+\alpha^3 z^3+\cdots\]

Similarly we have

(4)
\[\frac{1}{1-\beta z}=1+\beta z+\beta^2 z^2+\beta^3 z^3+\cdots\]

If we add (3) \(\times A\) and (4) \(\times B\), the left is

\[\frac{A}{1-\alpha z}+\frac{B}{1-\beta z}=\frac{A+B+(-A\beta-B\alpha)z}{1-(\alpha+\beta)z+\alpha\beta z^2}\]

and the right is

\[(A+B) + (A\alpha+B\beta)z + (A\alpha^2+B\beta^2)z^2 + \cdots\]

Then we realize that if we find the solutions to these two equations:

(5)
\[\begin{align} z &= A+B+(-A\beta-B\alpha)z \\ 1-z-z^2 &= 1-(\alpha+\beta)z+\alpha\beta z^2 \end{align}\]

then

\[\begin{align} G(z) = \frac{z}{1-z-z^2} &= \frac{A+B+(-A\beta-B\alpha)z}{1-(\alpha+\beta)z+\alpha\beta z^2} \\ &= \frac{A}{1-\alpha z}+\frac{B}{1-\beta z} \\ &= (A+B) + (A\alpha+B\beta)z + (A\alpha^2+B\beta^2)z^2 + \cdots \end{align}\]
\[\]

obviously \(g_n=A\alpha^n+B\beta^n\) and we'll be done.

Now all we have to do is to solve (5). Fortunately it's no hard job, first we realize that:

\[\begin{align} A+B &= 0 \\ -A\beta-B\alpha &= 1 \\ \alpha+\beta &= 1 \\ \alpha\beta &= -1 \end{align}\]

therefore

\[\begin{align} \alpha &= \frac{1\pm\sqrt{5}}{2} \\ \beta &= \frac{1\mp\sqrt{5}}{2} \\ A &= \pm\frac{1}{\sqrt{5}} \\ B &= \mp\frac{1}{\sqrt{5}} \end{align}\]

in which

Therefore

\[\begin{align} \alpha &= \phia \\ \beta &= \phib \\ A &= \frac{1}{\sqrt{5}} \\ B &= -\frac{1}{\sqrt{5}} \end{align}\]

We can expand \(G(z)\) now:

\[\begin{align} G(z) &= \frac{z}{1-z-z^{2}} \\ &= (A+B) + (A\alpha+B\beta)z + (A\alpha^2+B\beta^2)z^2 + \cdots \\ &= 0 + \frac{\phia-\phib}{\sqrt{5}}z + \frac{\phia^2-\phib^2}{\sqrt{5}}z^2 + \cdots \end{align}\]

We can read off the coefficient of \(z^n\):

\[g_n=\frac{\phia^{n}-\phib^{n}}{\sqrt{5}}\]

In other words, the \(n\)th Fibonacci number is \(\frac{\phia^{n}-\phic^{n}}{\sqrt{5}}\).

Summary

This is amazing. We introduce \(z^n\), then we use \(z^n\) and the unknown \(g_n\) (here \(g_n\) is \(F_n\)) to construct a \(G(z)\), finally we expand \(G(z)\) to get \(g_n\). It's like music: we have a subject, then we develop it and eventually we come back to it.

Please note that \(z\) and \(G(z)\) are meaningful only because we care about the coefficients of \(z^n\). We don't care what \(z\) is, neither do we care what \(G(z)\) is. What we care is the expanded form of \(G(z)\), so once we have a \(G(z)\), we focus on how to expand it.

Generating function is beautiful and very powerful. You must have seen this in this tutorial. If you want to learn more, I suggest you read [GKP]. This tutorial is actually a note I made when I read the book. Fibonacci numbers are amazing. If you read [GKP], you'll find more discussions in Chapter 6 and Chapter 7.

[GKP](1, 2) Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1989; second edition, 1994.