Generating Functions and Recurrence Relations

In another note we commented on the (small) Schröder numbers, and described how their generating function

is derived from their combinatorial definition. We also mentioned some recurrence relations satisfied by these numbers. To show how those recurrences are related to the generating function, note that the derivative of g(x) is

Therefore, we can write g(x) and g′(x) as

where Q represents the square root of x² – 6x + 1. We seek a relationship between g, g′, and x that does not involve square roots. One way of proceeding is to simply solve each of these two equations for Q and then equate those two expressions. This leads to

Now, letting s_j denote the jth small Schröder number, we know the functions g and g′ have the series expansions

Substituting these expressions for g and g′ into the previous equation and setting the coefficient of each power of x in the resulting expression to zero, we get the set of conditions

Therefore we have the convolution recurrence relation

However, this is not the only recurrence relation satisfied by this sequence. Note that the relation between g and g′ expressed by equation (1) is non-linear in the sense that it involves the product of g and g′. A simpler recurrence would result if we could find a linear equation relating those to functions. Suppose we multiply through the equation for g(x) by 4, and we multiply through the equation for g′(x) by 4Q². This gives

Since Q² = x² – 6x + 1, we can make this substitution into the right hand equation, along with the expression for Q given by the left hand equation, to arrive at

Expanding and simplifying, this can be written in the form

Substituting the series expansions for g and g′ into this equation and setting the coefficients of each power of x in the resulting expression to zero, we get the sequence of conditions

and so on. In other words, we have the recurrence

We can also proceed in the opposite direction, i.e., given a recurrence relation for a sequence of numbers, we can determine the generating function for that sequence. As we’ve seen, a given sequence can satisfy many different recurrence relations, so there is not a unique starting point. Given the convolution recurrence relation (3), we begin by multiplying each of the individual relations (2) by the corresponding power of x as follows:

Summing these equations together, we get

Each of the summations is, by definition, the generating function g(x), so making those substitutions and re-arranging terms, we have

Now if we differentiate this equation we get

which we note is identical to equation (1). To solve this differential equation, we first make a change of variables, defining a function h(x) and its derivative in terms of g(x) and its derivative as follows:

Notice that if we set A(x) = 2, B(x) = –(1–x), and C(x) = x, the differential equation written in terms of h is simply h′ = 0, which implies that h is an arbitrary constant of integration. Inserting the values of A, B, C, into the equation for h and solving for g, we get

which of course (with h = 0 to match the initial values) is the original generating function for the small Schröder numbers.

If, on the other hand, we had been given the second-order recurrence relation (5), we would proceeding in a similar way, multiplying each of the individual relations in (4) by the respective power of x, giving the equations

Then we sum all these equations as follows:

The two summations on the right side can each be split into two, one with a factor of n and the other without. We also note that the summations factored by n can be expressed in terms of the derivative of the generating function using the relation

Substituting for the summations in the previous equation therefore gives

Taking s₁ = 1, re-arranging terms, and dividing through by x, we have

To solve this differential equation we might try to make use of the previous method, defining a new function h = Ag² + Bg + C, in terms of which the equation is trivial. Admittedly in this case  the equation is linear, i.e., there are no terms with products of g or its derivatives, so we must put A = 0, but this is not an impediment. However, if we set B to the coefficient of g′ in the above equation, the coefficient of g would have to be B′ = 2x – 6, which it isn’t, so the solution is not quite as easy as in the previous example. To make the method work, we make use of an integrating factor, i.e., we multiply through by an (initially) arbitrary function R(x) to give

Now we set B(x) equal to the coefficient of g′ in this equation, and then determine what R(x) must be in order for B′(x) to be the coefficient of g. The derivative of B is

Setting this equal to the coefficient of g, we get the following condition on the function R:

Re-arranging terms, this gives

Integrating both sides, we get

Taking the exponential of both sides gives

Therefore, we have

Integrating the expression for C′(x) gives

With these expressions for B and C, the differential equation written in terms of the variable h = Bg + C is simply h′ = 0, so h is a constant, and we have

where the constant h must equal –1/4 in order to match the initial value. Thus we’ve arrived (again) at the original generating function.

The integrations involved in this example were elementary, but only because the coefficients satisfied certain conditions. In general, if we have a sequence defined by the initial values s₀, s₁ and the second-order recurrence relation

where A through F we find that the integration involved in determining the integrating factor R(x) is elementary if and only if

If A, C, and E all non-zero, this is equivalent to the condition

When this condition is met, the above procedure leads to the generating function

where h is a constant determined by the initial values. In order for the integral in this expression to have a simple “closed-form”, the quantities B/A and (F/E) – (B/A) must both be integers, and the latter should be an odd integer to make the integral “elementary”. This implies that F/E must be an integer, and therefore (from the earlier condition) the quantity D/C must be either a whole or half integer. For the Schröder numbers we had A = 1, B = 0, C = –6, D = 9, E = 1, and F = –3, which satisfy the stated conditions.

For another example, consider a series of numbers with the initial values s₀ = s₁ = 1 and satisfying the recurrence

The coefficients satisfy the stated conditions, so the above formula can be used to give the generating function

Expanding this function into a series, we get

It can be verified that the coefficients of this power series do indeed satisfy the given recurrence relation.

Return to MathPages Main Menu