11.2. 11.2 Generating functions and recurrence equations

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.

11.2.1. 11.2.1 Definition and operations

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

that is

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 .

Example 11.7 Let . Then

Multiplication. If and are generating functions, then

where .

Special case. If for all natural numbers , then

If, in addition, for all , then

Derivation.

Example 11.8 After differentiating both sides of the generating function

we obtain

Integration.

Example 11.9 Let

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

Example 11.10 Let . Then

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

Then

and

where is a natural number.

11.2.2. 11.2.2 Solving recurrence equations by generating functions

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

If (11.14) can be written as and can be solved for , then can be expanded into series in such a way that can be written in closed form, equation (11.14) can be solved.

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.

11.2.2.1.  Linear nonhomogeneous recurrence equations with constant coefficients.

Multiply both sides of equation (11.8) by . Then

Summing up both sides of the equation term by term we get

Then

Let

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.

Example 11.11 Solve the following equation using the above method

After multiplying and summing we have

and

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

Thus

therefore

Footnote. For decomposing the fraction into partial fractions we can use the Method of Undetermined Coefficients.

11.2.2.2.  The number of binary trees.

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.)

Figure 11.2.  Binary trees with two and three vertices.

Binary trees with two and three vertices.


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

11.2.2.3.  The number of leaves of all binary trees of vertices.

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 ,

Thus

and since

we have

After the computations

and

11.2.2.4.  The number of binary trees with vertices and leaves.

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

Thus

or

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

thus

Since , only the negative sign can be chosen. After expanding the generating function we get

From this

Since for , it can be proved easily that . Thus

Using the formula

therefore

Thus

or

11.2.3. 11.2.3 The Z-transform method

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

But

where . Now, by expanding this partial fraction, we get

Denote the coefficient of by , then , so

or

After the transformation and using we obtain

where

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 .

Linear-Nonhomogeneous( )

  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  
                        RETURN
                      
                       
                  

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.

Example 11.12 Solve the recurrence equation

Multiplying both sides by and summing we obtain

or

Thus

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

Example 11.13 Solve the recurrence equation

Multiplying by and summing gives

so

that is

Then

The roots of the denominator are and . Let us compute and :

Since

raising to the th power gives

Exercises

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:

where .