The notion of generating functions and its application to solving recursive equations are very well-known. For reader who did not have a chance to get familiar with the topics, I recommend to take a look at very good book: Concrete Mathematics: A Foundation for Computer Science, by Ronald L. Graham, Donald E. Knuth, Oren Patashnik.
Generating functions are usually applied to single variable recursive equations. But actually, the technique may be extended to multivariate recursive equations, or even to a system of recursive equations. Readers who are familiar with one-variable case, may jump directly to the next post: Cracking Multivariate Recursive Equations Using Generating Functions.
The Generating Function for Fibonacci Sequence
Let’s consider the generating function’s application to Fibonacci numbers. The Fibonacci numbers could defined by the recursive expression:
$$f_n = f_{n-1} + f_{n-2} + [n=0]$$
We assume that for any $n < 0$, $f_n = 0$. The indicator $[n=0]$ equals to $1$ only if $n=0$. This definition produces the following sequence of the Fibonacci numbers: $1$, $1$, $2$, $3$, $5$, $8$, $13$, $\dots$. Note that sometime, the Fibonacci sequence is defined to start from 0, but it is really not important for the perpose of our discussion.
The generating function $\Phi(x)$ on a floating point variable $x$ is defined as the infinite sum:
$$\Phi(x) = \sum_{n\geq 0} f_n x^n$$
Usually, it is hard to develop an intuition why it is defined that way and why it could be useful. So let’s just focuse on what we can do with this, and let’s start from substituting the defintion of Fibonacci recursion into the formular of generating function:
$ \Phi(x) $ $ = \sum_{n\geq 0} f_n x^n $ $ = \sum_n f_n x^n $ $ = \sum_n (f_{n-1} + f_{n-2} + [n=0]) x^n $ $ = \sum_n f_{n-1} x^n + \sum_n f_{n-2} x^n + \sum_n [n=0] x^n $ $ = x \sum_n f_{n-1} x^{n-1} + x^2 \sum_n f_{n-2} x^{n-2} + 1 x^0 $ $ = x \sum_n f_n x^n + x^2 \sum_n f_n x^n + 1 $ $ = x \Phi(x) + x^2 \Phi(x) + 1 $
And we can obtain the generating function for $f_n$:
$$\Phi(x) = \frac{1}{1 - x - x^2}$$
Two Closed Forms for Fibonacci Relation
Nice expression, but what can we do with this “magic” formula? We can hack it in two different ways, and depending on our next step, we can get different closed forms for $f_n$.
The 1st closed form
One of the standard ways is to split the fraction into two simple ones of the form: $\frac{A}{x+B}$. Note that the roots of the quadratic equation: $1 - x - x^2 = 0$ are $x_0=-\phi$ and $x_1=\phi^{-1}$, where $\phi$ is the Golden Ratio:
$ \phi = \frac{1 + \sqrt{5}}{2} = 1.618\dots $.
Let’s do a quick test:
$ -(x-x_0) (x-x_1) $ $ = -(x+\phi) \left(x-\phi^{-1}\right) $ $ =-x^2 - x\cdot\left(\phi - \phi^{-1}\right) + 1 $ $ = -x^2 - x + 1 $.
Now we can transform the generating function $\Phi(x)$ as follows:
$\Phi(x)$ $ = \frac{1}{1-x-x^2}$ $ = -\frac{1}{(x+\phi) \left(x-\phi^{-1}\right)}$ $ = \frac{A}{x+\phi} - \frac{A}{x-\phi^{-1}}$ $ = A\cdot\phi^{-1} \frac{1}{1+x\cdot\phi^{-1}} + A\cdot\phi \frac{1}{1 - x\cdot\phi}$,
where $A=\frac{1}{\phi+\phi^{-1}}$.
The next trick is to apply the infinite series $\frac{1}{1-z} = \sum_n z^n$ to each of two expressions and to simplify the sums:
$\Phi(x) $ $ = A\cdot\phi^{-1} \sum_n \left(-x\cdot \phi^{-1}\right)^n + A\cdot\phi \sum_n (x\cdot\phi)^n $ $ = A\cdot\phi^{-1} \sum_n (-\phi)^{-n} x^n + A\cdot\phi \sum_n \phi^n x^n $ $ = \sum_n A\cdot\left(\phi^{-1} (-\phi)^{-n} + \phi\cdot \phi^n \right) x^n $ $ = \sum_n A\cdot\left(\phi^{n+1} - (-\phi)^{-n-1}\right) x^n $ $ = \sum_n \frac{\phi^{n+1} - (-\phi)^{-n-1}}{\phi+\phi^{-1}} x^n $.
The term before $x^n$ is nothing but $f_n$, which gives the first closed form for the Fibonacci relation:
$$f_n=\frac{\phi^{n+1} - (-\phi)^{-n-1}}{\phi+\phi^{-1}}$$
The 2nd closed form
Another way to crack the generating function is to apply the infinite series $\frac{1}{1-z} $ $= \sum_n z^n$ directly to the generating function:
$ \Phi(x) $ $ = \frac{1}{1 - x - x^2} $ $ = \frac{1}{1 - (x+x^2)}$ $ = \sum_n (x+x^2)^n $ $ = \sum_n (1+x)^n x^n $
Now we can use the Binomial formula: $(a + b)^n = \sum_{0\leq k\leq n} {n \choose k} a^{n-k} b^k$ in order to expand $(1+x)^n$:
$ = \sum_{0\leq k \leq n} {n \choose k} x^{n+k} $.
By introducing the new variable $t=n+k$, we obtain
$ = \sum_{t/2 \leq n \leq t} {n \choose t-n} x^t $ $ = \sum_t \sum_{n=t/2}^t {n \choose t-n} x^t $
Which gives us another closed form for the Fibonacci numbers:
$$f_t = \sum_{n=t/2}^t {n \choose t-n}$$
Conclusion
Believe it or not, but the two forms define the same Fibonacci sequence.
$$ f_n = \frac{\phi^{n+1} - (-\phi)^{-n-1}}{\phi+\phi^{-1}} $$
$$ f_n = \sum_{i=n/2}^n {i \choose n-i} $$
Just notice how powerful the generating functions are! An interested reader can try to prove by induction the correctness of the relations above. If you liked the topic, you are wellcome to take a look at the next post where we extend the tools to mutivariate recursions.