[seqfan] Re: Generating functions

Ed Jeffery ed.jeffery at yahoo.com
Fri Dec 9 23:47:45 CET 2011

In response to comments by William Keith and Marc LeBrun:

Most people (including myself) who have studied and authored integer
sequences have at least a basic knowledge of the notion of a generating
function, its expansion to formal power series) and its associated recurrence
relation if it exists. I am also familiar with Herbert Wilf's work "generating-
functionology," but I have to say that the abstraction presented by his 

notation for the coefficient a_k of x^k in a power series obscured what I was 

trying to understand at the time, so I went to other sources.

On Dec 8, I wrote
( http://list.seqfan.eu/pipermail/seqfan/2011-December/016034.html ):
"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 opinion
about this?"

William Keith responded

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

William, you lost me there. Did you mean "...in the set of all polynomials
over the rationals" (the integers are not a field)? Otherwise, can you define
a typical element of your field?

Let S = {c_0 + c_1*x + ... + c_k*x^k + ...} be the set of all formal power
series in x. Let

A = A(x) = a_0 + a_1*x + ...


B = B(x) = b_0 + b_1*x + ...

Define addition and multiplication (Cauchy product) of A, B in S in the
usual way, that is, by

A +/- B = Sum_(n=0,1,...) (a_n +/- b_n)*x^n


A*B = Sum_(k=0,1,...) a_k*b_(n-k)*x^k,

respectively, with addition commutative and multiplication distributive. Clearly
0,1 in S as well.

Let P = [Sum_(n=0,1,...) p_n*x^n]  in S. Then 1/P in S, if and only if p_0 <> 0.
Therefore S is a ring, not a field. However, for the set V = {Q in S : q_0 <> 0},
the set of all invertible elements in S, its elements may satisfy all required
properties of a field, but you weren't clear about this definition.

Also, yes, 1/(1-x-x^2) = 1-x-x^2, however, I was trying to give the example for
1/F, where F=F(x)=(1+x+2*x^2+...)  in S is the Fibonacci series. In that case,

1/F = 1-x-x^2,

that is, F*(1-x-x^2) = 1, as I thought I said. What I was getting at is that if a
sequence is known but its generating function and recurrence formula are not
known, letting f,g in V subset S, if f is the power series with coefficients given
by our sequence, and if the generating function for f is of the form h/g, with h = 1,
then the procedure I outlined should give the series g (hopefully a polynomial),
provided we are given enough terms of the sequence, In the procedure I described,
the series g is found by successive approximation for which the method is well-
defined. However, this is a conjecture since I can't provide proof. I found nothing
in Herbert Wilf's book giving this procedure.

On the other hand, for the series f=h/g, if f,g,h in V and deg(h)<>0 (with h not
known either), then g is going to be relatively tough to determine by the procedure
I suggested since it is often the case that g turns out to not be a polynomial.
However, the procedure should still give the reciprocal 1/f, if all coefficients given
by our infinite sequence used.

On Dec 8, Marc LeBrun wrote
( http://list.seqfan.eu/pipermail/seqfan/2011-December/016036.html):

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

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?

Marc also wrote:

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

Let f,g,h in S and suppose f=h/g is the series representation for our sequence.
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). That is, since clearly f,g in V, f*g = 1, and if
f is an infinite series, then g is a polynomial if and only if our sequence has a
(finite) recurrence relation. How does one prove this assertion?


Ed Jeffery

More information about the SeqFan mailing list