[seqfan] Generating functions

[Ed Jeffery]

Seqfans,

Most of you have more experience than I do regarding generating functions (functions expanded to formal series) for integer sequences. So maybe some of you can shed some light on what techniques to use when searching for them.

For a series of the form

S = a_0 + a_1*x + a_2^x^2 + ...,

in which the a_r are integers, if its generating function F(x) exists and it is "simple," then it is of the form

F(x) = 1/G(x)

where G(x) is a polynomial of degree m > 0 in x. I will not discuss the case for which G(x) is also an infinite series, although that is also very interesting. If instead

F(x) = H(x)/G(x)

where H(x) is also a polynomial of degree d > 0, then F(x) is not simple. I'll try to make the distinction between simple and not simple clear.


Now, this I know: if an integer sequence has a recurrence relation, then it also has a generating function. Some of the sequences I encounter are suspected of having both since, unless I am wrong, the existence of one implies the other.

If a sequence is simple, then its generating function is often easy to deduce. One can use the fact (which I can't prove) that there exists some (hopefully finite) series A(x) such that


S*A(x) = 1,

which means that, in some sense, A(x) is an inverse of S. If you have software that can expand a generating function to series and also expand and factor polynomial expression algebraically, then you will see that the assertion is true (but perhaps not always). I'll give a simple example.

Consider the Fibonacci sequence. Eliminating leading zeros, this sequence (with offset = 0) is Fib = {1,1,2,3,5,8,13,...). Let

f(x) = 1 + 1*x + 2*x^2 + 3*x^3 + 5*x^4 + ... + Fib(n)*x^n

be an approximation to the desired series. Assuming n is large enough, and assuming a generating function for Fib exists (we know it does) there exists a positive integer k and a function a(x) such that

(1)     f(x) * a(x) = 1 + b_k*x^k + b_(k+1)*x^(k+1) + ...    (k>n)


wherein all of the coefficients b_j for 0 < j < k vanish. Letting n -> infinity, we will see that the value of k follows it, and the nonzero terms in the series (1) shift farther and farther to the right. We can deduce a(x) by successive approximation. The steps are sketched as follows.

Start


(i) Make some assumption about n so it will be large enough, otherwise n may have to be increased on the fly. 


Set MaxZeros = z, 


where z is the maximum number of successive zero coefficients that will be checked to verify the generating function, beyond which we assume it to be accurate.


(ii) Put a_0(x) = 1; Zeros = 0, the number of zero coefficients encountered so far.


(iii) Loop (a label)


(iv) v = v + 1. 


(v) Expand the product 

  

        p_v(x) = f(x)*a_(v-1)(x) 


so it is no longer factored and arrange the terms in order by exponent smallest to largest, viz.,

(vi) p_v(x) = c_0 + c_1*x + ... + c_q*x^q    (since it is a polynomial)


(Note that the coefficient c_v can be negative as we shall see.)


(vii)  If c_v = 0, then Zeros = Zeros +1


(viii) a_v(x) = a_(v-1)(x) - c_v*x^v. 


If Zeros <> MaxZeros, then Go to "Loop" else G(x) = a_v(x); Exit.

However many terms there are in the denominator of the generating function determines how many passes through the above procedure that are required. That is, if G(x) is a degree d polynomial, then the procedure will loop d times (I think). The following is the Fib example worked out. Let >> denote the expansion of a factored expression to its full polynomial expression (vi).


n = 11
f(x) = 1 + 1*x + 2*x^2 + 3*x^3 + 5*x^4 + ... + 144*x^11
a_0(x) = 1  (first approximation); MaxZeros = n (my preference)

for v = 1,2,3 we get the following

v=1
p_1(x)=f(x)*a_0(x) >> 1 + 1*x + 2*x^2 + 3*x^3 + 5*x^4 + ... + 144*x^11
c_1<>0
a_1(x)=a_0(x)-c_1*x = 1 - x  (second approx.)
Zeros<>MaxZeros
v=2
p_2(x)=f(x)*a_1(x) >> 1 + x^2 + 2*x^3 + 3^x^4 + ... + 55*x^11 - 144*x^12
c_2<>0
a_2(x)=a_1(x)-c_2*x^2 = 1 - x - x^2  (third approx., which is already our desired polynomial)
Zeros<>MaxZeros
v=3
p_3(x)=f(x)*a_2(x) >> 1 - 233*x^12 - 144*x^13 (and you can see how the zero coefficients have extended beyond n=11, which is a pretty good indicator that our generating function (rather the characteristic polynomial in the denominator of the generating function) is correct.

Now the zeros are evaluated and counted until exiting, and that's all there is to it unless I made a mistake.

And we all know that expanding 1/(1-x-x^2) to series gives the Fibonacci sequence. But, given enough of its terms, did you know that expanding the inverse of the  Fibonacci series to series, you get the characteristic polynomial 1-x-x^2. Using the above procedure we can also find an approximation to a sort of inverse A of S, such that the expansion of 1/A to series yields S (and the converse is true, I assume). I hesitate to use the notation S^(-1) since this should mean 1/S. This may be some type of inverse in the polynomial ring. Any theorists out there with an opinoin about this?

Finally, my question is this: what are we supposed to do when the generating function for a sequence is clearly not simple? From my perspective, that problem is just as messy and futile as factorization because a(x) will tend to be an infinite series more often than not.

Regards,

Ed Jeffery