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 x2 – 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 sj 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 4Q2. This gives Since Q2 = x2 – 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 s1 = 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 = Ag2 + 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 s0, s1 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 s0 = s1 = 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