[seqfan] Re: Generating functions

[Marc LeBrun]

Forgive me if I haven't read these messages carefully, or I'm restating the
obvious, but isn't this well-understood "generatingfunctionology"?

To recap: 

If a sequence is defined by a "k-th order linear recurrence"

  a(n) = sum c_j a(n-j) over j=0..k-1, for n>=k

then the generating function is a ratio of two polynomials (aka "rational"):

  g(x) = p(x)/q(x).

The coefficients of p will be related to the k initial values a(0)..a(k-1)
and the coefficients of q will be related to the k recurrence weights c_j.

The c_j can be easily found by solving k simultaneous linear equations.


If the degree k isn't known then one way to find it is by trying successive
values for k, solving for the c_j and then checking to see if the terms the
recurrence predicts match the rest of the sequence.

Of course if only a finite number of a(n) are given there is always a way to
match ALL of them with SOME linear recurrence--just like they can all also
be matched with a polynomial--so it doesn't really tell you anything unless
you can test the hypothesized recurrence against at least one further term.


I think this is essentially how superseeker looks for possible linear
recurrences, and I believe it's pretty much what you seem to be describing
as well.

Note that this method isn't restricted to reciprocal polynomials, which  are
just the special case where p(x)=1, but works for all rational g(x).

Alas I'm unable to grasp the rest of the discussion about "simple" sequences
etc, so will only note that this pattern of solving for coefficients also
may work with other types of generating functions besides rational, and that
sometimes computer algebra systems can even give you symbolic expansions.