[seqfan] Re: Generating functions

[Marc LeBrun]

>="Ed Jeffery" <ed.jeffery at yahoo.com>



> Marc, without knowledge of p(x) or q(x) or a recurrence relation:
> (i) What is the relation of the coefficients of p(x) to the initial conditions
> for a typical sequence having some kind of recurrence relation?
> (ii) Can you express your answer to (i) mathematically?

Yes, taking "mathematically" to mean as expressions in terms of the sequence
value parameters.

I'll try to be helpful, but I am not well-positioned right now to do all the
explicit algebra.  However you will be able to easily work out the details.

If the a(n) values obey a d-term *linear* recurrence

  a(n+1) = C0 a(n) + C1 a(n-1) + ... + Cd a(n-d)

then g(x)=p(x)/q(x) involves 2d-1 undetermined coefficients (d from p(x),
plus d from q(x), less one because scaling both top and bottom by the same
amount gives the same g(x)).

If you write g(x)=p(x)/q(x) as the ratio of two polynomials with symbolic
coefficients, and then expand g(x) as a Taylor series (by hand, or in some
algebra package) you will get an infinite sequence of explicit symbolic
expressions for the coefficients of g(x) in terms of the coefficients of
p(x) and q(x).  

You can then set up simultaneous equations equating the first 2d-1 of these
expressions to the corresponding symbolic a(n) and solve that system.

This will produce explicit 2d-1 symbolic expressions for the polynomial
coefficients in terms of the sequence values.

Of course there may be more elegant ways to get these expressions (which are
doubtless spelled out in various texts), but they are straightforward to
derive yourself by just slogging through the linear algebra.

> Although it was not necessary, I defined a "simple" sequence as one for which
> h=1. If h=1 and the sequence happens to have a recurrence relation, then the
> procedure I described should yield g in a finite number of steps (without
> knowing the recurrence relation in advance).
> [...] How does one prove this assertion?

If g(x) is rational, the procedure above explicitly yields p(x)/q(x) in some
finite number of steps.

(The "simplifying" assumption that p(x)=1 only has the effect of
predetermining d of the 2d-1 free values.  But, as you note, this isn't
necessary--the fully general case just involves more of the same grinding).

You can find d by successively trying d=1,2,3,... until the output
recurrence  correctly predicts all the known input values of a(n).  This
"outer loop" too is finite.

There may be more interesting ways to skin this cat--perhaps binary search
for d, or maybe some kind of symbolic Newton's method--who knows?