[Seqfan] Re: [Seqfan] Re: Need some help from Fibonacci experts...

[Ralf Stephan]

>   Now, how can I get P(x)/Q(x) if I suspect them to be polynomials
>   (which seems to be the case for the functions I use) ? Ie. how
>   did you get yourself to find the ogf of my functions from this
>   last step ?

Also with LLL!  This routine

ggf(v)=local(l,m,p,q,B);l=length(v);B=floor(l/2);if(B<4,return(0));m=matrix(B,B,x,y,v[x-y+B+1]);q=qflll(m,4)[1];if(length(q)==0,return(0));p=sum(k=1,B,x^(k-1)*q[k,1]);q=Pol(Pol(vector(l,n,v[l-n+1]))*p+O(x^(B+1)));if(polcoeff(p,0)<0,q=-q;p=-p);q=q/p;p=Ser(q+O(x^(l+1)));for(m=1,l,if(polcoeff(p,m-1)!=v[m],return(0)));q

uses the fact that every sequence having a rational g.f. obeys a linear
recurrence with constant coefficients. That is, you fill the matrix
with shifted copies of the sequence, then LLL will find the recurrence.

I cannot stress enough on the list the beautiful fact that the denominator
polynomial of the rational g.f. already contains everything about the
recurrence and vice versa. It can be simply read off. Knowing this by
heart makes many questions unnecessary.


ralf