The Fibonacci generating function
The recurrence relation for the Fibonacci sequence is ubiquitous:
\[F_n = F_{n-1} + F_{n-2},\]for \(F_0 = 0\) and \(F_1 = 1\).
Suppose we want to know the \(n\)th Fibonacci number (\(F_n)\) without dealing with all the recursion above. How can that be found?
What follows is a neat derivation for \(F_n\) using generating functions. The setup was taken from both Cormen, Leiserson and Rivest (1st Edition), and Wilf’s “Generating Functionology.” If you’d like to fill in the blanks in their derivations, best stop reading here! Otherwise, let’s see how it works.
Suppose we want the generatiing function for the Fibonacci sequence
\[0, 1, 1, 2, 3, 5, 8, 13, \ldots\]By definition, the generating function
\[\begin{align} F(z) & = \sum_{n=0}^\infty a_nz^n, \\ & = 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + \cdots. \tag{1} \end{align}\]This isn’t particularly helpful, let’s get a better solution for \(F(z)\), we’ll multiply \(F(z)\) by \(z\):
\[zF(z) = z^2 + z^3 + 2z^4 + 3z^5 + 5z^6 + \cdots. \tag{2}\]Subtracting 2 from 1 gives us
\[\begin{align} F(z) - zF(z) & = z - z^3 +z^4 +2z^5 +3z^6 + \cdots \\ & = z + z^2(0 + z + z^2 + 2z^3 + 3z^4 + \cdots) \\ & = z + z^2F(z). \end{align}\]You should see a nice, closed form solution now:
\[F(z) = \frac{z}{1 - z - z^2}.\]Interesting, but not useful. We can go further, let’s work out a partial fraction decomposition.
\[\newcommand{\phihat}{\hat\phi}\]First we determine the roots of the equation
\[1 - z - z^2 = 0,\]which for easier factoring we want to write as
\[-(z^2 + z - 1) = 0.\]By the quadratic formula, we find the roots
\[z_1 = \frac{-1 - \sqrt{5}}{2} = -\phi,\]and
\[z_2 = \frac{-1 + \sqrt{5}}{2} = -\phihat.\]Note that \(\phihat = 1 - \phi\), and \(\phi\phihat = -1\). To check the result, plug the roots back into the equation:
\[\begin{align} -(z^2 + z - 1) & = -(z + \phi)(z + \phihat)\\ & = -(z^2 + \phi z + \phihat z + \phi\phihat)\\ & = -(z^2 + \phi z + z - \phi z - 1). \end{align}\]Now that we have the roots, we can decompose the Fibonacci generating function \(F(z)\) into its constituent fractions. However, for reasons which will become apparent shortly, let’s do a little more work to rewrite the factors into a convenient form. Starting with the factors above,
\[\begin{align} F(z) & = \frac{-z}{(z + \phi)(z + \phihat)}\frac{1/\phi\phihat}{1/\phi\phihat}\\ \\ & = \frac{z}{\cfrac{(z + \phi)}{\phi}\cfrac{(z + \phihat)}{\phihat} }\\ \\ & = \frac{z}{\left(\cfrac{z}{\phi} + 1\right)\left(\cfrac{z}{\phihat} + 1\right)}.\\ \end{align}\]Note that \((\phi\phihat/\phi\phihat)(z/\phi) = -\phihat z\) and \((\phi\phihat/\phi\phihat)(z/\phihat) = -\phi z\) and substitute to obtain
\[F(z) = \frac{z}{(1 - \phi z)(1 - \phihat z)}.\]Using partial fraction decomposition,
\[\frac{z}{(1 - \phi z)(1 - \phihat z)} = \cfrac{\alpha}{1 - \phi z} + \cfrac{\beta}{1 - \phihat z},\]and we can write
\[z = \alpha(1 - \phihat z) + \beta(1 - \phi z).\]Solving first for \(\alpha\), let \(z = 1/\phi\):
\[\begin{align} 1/\phi & = \alpha(1 - \phihat/\phi),\\ 1 & = \alpha(\phi - \phihat).\\ \end{align}\]After convincing yourself that \((\phi - \phihat) = \sqrt{5}\), it’s easy to see
\[\alpha = \frac{1}{\sqrt{5}}.\]By similar computation,
\[\beta = -\frac{1}{\sqrt{5}}.\]The end result of these computations produces the very useful
\[F(z) = \frac{1}{\sqrt{5}}\left(\cfrac{1}{1 - \phi z} - \cfrac{1}{1 - \phihat z}\right).\]Continuing, recall for \(0 < y < 1\)
\[\sum_{n=0}^\infty y^n = \frac{1}{1 - y},\]Choose \(y = \phi z\) where \(z > 1/\phi\) and write
\[F(z) = \frac{1}{\sqrt{5}}\sum_{n=0}^\infty \phi^n z^n - \frac{1}{\sqrt{5}}\sum_{n=0}^\infty \phihat^n z^n,\]resulting in an expression for the \(n\)th coefficient, that is, the \(n\)th Fibonacci number:
\[F_n = \frac{1}{\sqrt{5}}(\phi^n - \phihat^n).\]That’s all for now.