Sequence relating to Pell numbers; a new technique

[Ralf Stephan]

Mitch Harris:
> >Let G(n) = a G(n-1) + b G(n-2), with G(0) and G(1) the given base cases 
> >(i.e. constants but... er... variable).
> >
> >Then G(n) happens to be 
> >  G(1) F(n) + G(0) F(n-1) (proof by induction)
> 
> Er...no, that's pretty wrong. It is certainly true when a = b = 1.

Not so fast[*]! You can say there is an infinite number of 2nd order
linear recurrences that are expressible using F(n)/L(n) IF you allow for
arguments that are linear polynomials of n, and other constructs:

a=3, b=-1, a(0)=1, a(1)=2, a(n) = F(2n+1)  (A001519)
a=4, b=-1  ...                    F(3n+...)
a=7, b=-1  ...                    F(4n+...)
a=...
=====
Now, the sequence of a in this list, well, is the Lucas numbers.

Next, take sequences of form k^n*F(l*n+...), then F^k, etc...
e.g. 2^n*L(4n) has a=14, b=-4!

Just use your CAS and guessgf, if you have Pari take this:

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

It takes a vector of numbers, at best >20-30 numbers.
If that has no rational ogf, it will return zero.


Best,
ralf
[*] If you suffer from the sigh-mailed-too-fast syndrome, use UUCP, it
helps. I'm regularly deleting mails from my queue.