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^{2} – 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 nonlinear 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^{2}. This gives 

_{} 

Since Q^{2} = x^{2} – 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 rearranging 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) = (1x), 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 secondorder 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} = 1, rearranging 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^{2} + 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: 

_{} 

Rearranging 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_{0}, s_{1} and the secondorder 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 nonzero, 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 “closedform”, 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_{0} = s_{1} = 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. 
