[seqfan] Re: Generating functions

[William Keith]

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?

It's not an inverse in the ring of polynomials, it's an inverse in the
field of polynomials.  1-x-x^2 is exactly the inverse of the Fibonacci
generating function in the field of polynomials over the integers.


> 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
>

"The sequence you seek has a recurrence relation of the form F(n) = c_1
F(n-1) + c_2 F(n-2) + ... + c_k f(n-k) for some finite k" is equivalent to
"the generating function for F is 1/P(x) for some polynomial x."  If these
statements are true, I am pretty sure your procedure will eventually find
P, assuming the margin at the end is larger than the degree of P.  If these
statements are not true, a guessing procedure needs to be considerably more
clever.  For example, if you suspect that the recurrence exists but is
quadratic in F, there would need to be several more variables associated to
that degree in F.  Attempting to find a polynomial P would simply result in
an infinite power series.

Cordially,
William Keith