Generating functions can be used, among others, to solve recurrence equations, count objects (e.g. binary trees), prove identities and solve partition problems. Counting the number of objects can be done by stating and solving recurrence equations. These equations are usually not linear, and generating functions can help us in solving them.
Associate a series with the infinite sequence the following way
This is called the generating function of the sequence .
For example, in case of the Fibonacci numbers this generating function is
Multiplying both sides of the equation by , then by , we obtain
If we subtract the second and the third equations from the first one term by term, then use the defining formula of the Fibonacci numbers, we get
The correctness of these operations can be proved mathematically, but here we do not want to go into details. The formulae obtained using generating functions can usually also be proved using other methods. Let us consider the following generating functions
The generating functions and are equal, if and only if for all natural numbers.
Now we define the following operations with the generating functions: addition, multiplication by real number, shift, multiplication, derivation and integration.
Addition and multiplication by real number.
Shift. The generating function
represents the sequence , while the generating function
represents the sequence .
Multiplication. If and are generating functions, then
Special case. If for all natural numbers , then
If, in addition, for all , then
After integrating both sides we get
Multiplying the above generating functions we obtain
where are the so-called harmonic numbers.
Changing the arguments. Let represent the sequence , then represents the sequence . The following statements holds
which can also be obtained by substituting by in . We can obtain the sum of the odd power terms in the same way,
Using generating functions we can obtain interesting formulae. For example, let . Then , which is the generating function of the Fibonacci numbers. From this
The coefficient of on the left-hand side is , that is the th Fibonacci number, while the coefficient of on the right-hand side is
after using the binomial formula in each term. Hence
Remember that the binomial formula can be generalised for all real , namely
which is the generating function of the binomial coefficients for a given . Here is a generalisation of the number of combinations for any real number , that is
We can obtain useful formulae using this generalisation for negative . Let
Since, by a simple computation, we get
the following formula can be obtained
where is a natural number.
If the generating function of the general solution of a recurrence equation to be solved can be expanded in such a way that the coefficients are in closed form, then this method is successful. Let the recurrence equation be
To solve it, let us consider the generating function
Now we give a general method for solving linear nonhomogeneous recurrence equations. After this we give three examples for the nonlinear case. In the first two examples the number of elements in some sets of binary trees, while in the third example the number of leaves of binary trees is computed. The corresponding recurrence equations (11.15), (11.17) and (11.18) will be solved using generating functions.
Multiply both sides of equation (11.8) by . Then
Summing up both sides of the equation term by term we get
The equation can be written as
This can be solved for . If is a rational fraction, then it can be decomposed into partial (elementary) fractions which, after expanding them into series, will give us the general solution of the original recurrence equation. We can also try to use the expansion into series in the case when the function is not a rational fraction.
After multiplying and summing we have
Since , after decomposing the right-hand side into partial fractions, the solution of the equation is
After differentiating the generating function
term by term we get
Footnote. For decomposing the fraction into partial fractions we can use the Method of Undetermined Coefficients.
Let us denote by the number of binary trees with vertices. Then , , (see Figure 11.2). Let . (We will see later that this is a good choice.)
In a binary tree with vertices, there are altogether vertices in the left and right subtrees. If the left subtree has vertices and the right subtree has vertices, then there exists such binary trees. Summing over , we obtain exactly the number of binary trees. Thus for any natural number the recurrence equation in is
This can also be written as
Multiplying both sides by , then summing over all , we obtain
Let be the generating function of the numbers . The left-hand side of (11.16) is exactly (because ). The right-hand side looks like a product of two generating functions. To see which functions are in consideration, let us use the notation
Then the right-hand side of (11.16) is exactly , which is . Therefore
Solving this equation for gives
We have to choose the negative sign because . Thus
Therefore . The numbers are also called the Catalan numbers.
Remark. In the previous computation we used the following formula that can be proved easily
Let us count the number of leaves (vertices with degree 1) in the set of all binary trees of vertices. Denote this number by . We remark that the root is not considered leaf even if it is of degree 1. It is easy to see that , . Let and , conventionally. Later we will see that this choice of the initial values is appropriate.
As in the case of numbering the binary trees, consider the binary trees of vertices having vertices in the left subtree and vertices in the right subtree. There are such left subtrees and right subtrees. If we consider such a left subtree and all such right subtrees, then together there are leaves in the right subtrees. So for a given there are leaves. After summing we have
By an easy computation we get
This is a recurrence equation, with solution . Let
Multiplying both sides of (11.17) by and summing gives
Since and ,
After the computations
A bit harder problem: how many binary trees are there with vertices and leaves? Let us denote this number by . It is easy to see that , if . By a simple reasoning the case can be solved. The result is for any natural number . Let , conventionally. We will see later that this choice of the initial value is appropriate. Let us consider, as in case of the previous problems, the left and right subtrees. If the left subtree has vertices and leaves, then the right subtree has vertices and leaves. The number of these trees is . Summing over and gives
For solving this recurrence equation the generating function
will be used. Multiplying both sides of equation (11.18) by and summing over , we get
Changing the order of summation gives
Step by step, we can write the following:
Let us try to find the solution in the form
where , , . Substituting in (11.19) gives a recursion for the numbers
We solve this equation using the generating function method. If , then , and so . Let . If is the generating function of the numbers , then, using the formula of multiplication of the generating functions we obtain
Since , only the negative sign can be chosen. After expanding the generating function we get
Since for , it can be proved easily that . Thus
Using the formula
When solving linear nonhomogeneous equations using generating functions, the solution is usually done by the expansion of a rational fraction. The Z-transform method can help us in expanding such a function. Let be a rational fraction, where the degree of is less, than the degree of . If the roots of the denominator are known, the rational fraction can be expanded into partial fractions using the Method of Undetermined Coefficients.
Let us first consider the case when the denominator has distinct roots . Then
It is easy to see that
where . Now, by expanding this partial fraction, we get
Denote the coefficient of by , then , so
After the transformation and using we obtain
Thus in the expansion of the coefficient of is
If is a root of the polynomial , then is a root of . E.g. if
If case of multiple roots, e.g. if has multiplicity , their contribution to the solution is
Here is the derivative of order of the function .
All these can be summarised in the following algorithm. Suppose that the coefficients of the equation are in array , and the constants of the solution are in array .
1 let be the equation, where is a rational fraction; multiply both sides by , and sum over all 2 transform the equation into the form , where , and are polynomials 3 use the transformation , and let the result be , where are are polynomials 4 denote the roots of by , with multiplicity , , , with multiplicity , , , with multiplicity , ; then the general solution of the original equation is , where . 5
If we substitute by in the generating function, the result is the so-called Z-transform, for which similar operations can be defined as for the generating functions. The residue theorem for the Z-transform gives the same result. The name of the method is derived from this observation.
Multiplying both sides by and summing we obtain
After the transformation we get
where the roots of the denominator are 1 with multiplicity 1 and 2 with multiplicity 2. Thus
Therefore the general solution is
Multiplying by and summing gives
The roots of the denominator are and . Let us compute and :
raising to the th power gives
11.2-1 How many binary trees are there with vertices and no empty left and right subtrees?
11.2-2 How many binary trees are there with vertices, in which each vertex which is not a leaf, has exactly two descendants?
11.2-3 Solve the following recurrent equation using generating functions.
( is the number of moves in the problem of the Towers of Hanoi.)
11.2-4 Solve the following recurrent equation using the Z-transform method.
11.2-5 Solve the following system of recurrence equations: