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

[Ralf Stephan]

> What is the best thing to read for learning more about generating functions ?

I would start with Wilf's generatingfunctionology which is also online:
http://www.math.upenn.edu/~wilf/DownldGF.html

If you miss some pieces, get them from Graham/Knuth/Patashnik.

But this may not help if you want solutions at once. Rather, if you
are of the pragmatic type, you should read about the LLL algorithm,
because generating functions are used only for finding which sort of
solution is possible, not the actual solution.

That means, if you suspect from ogf calculation that, e.g., 
  A066259(n) = F(n)F(n+1)^2 
can be expressed in terms of F(3n) and (-1)^n*F(n) ---which it can, see
A066258 and the comment about A001655 --- then the below procedure using 
LLL gives you the solution.
--------------------------
For integer i,j,k,l having reasonable values, e.g., -5 < i,j,k,l < 5, do:
1. Fill first column of matrix with a(n): v = [1, 2, 12, 45, 200, ...]
2. Fill other columns with sequences a(n) should be a linear combination
of. Take care those do not themselves have a linear solution. In this case,
we use f1(n)=F(3n+i), f2(n)=F(3n+j), f3(n)=(-1)^(n+k)F(n+k), 
f4(n)=(-1)^(n+l)F(n+l). 
3. Apply the LLL algorithm. The web has lots of info. Record if and which
solution is found.
4. (optional) Since you might get several solutions, you can weigh/sort them
to get the most "natural" looking. See my pari code below.

weight(q)=local(l);l=length(q~);sum(k=1,l,if(q[k,][1],q[k,][1]^2,-1000))
mw=10^11;oo=0;
for(k=-5,5,for(l=-5,5,m=matrix(length(v)-oo,3,n,j,if(j==1,(-1)^(n+k)*fibonacci(if(n+k<0,0,n+k)),if(j==2,fibonacci(if(3*n+l<0,0,3*n+l)),v[n])));q=qflll(m,4)[1];if(length(q)&&weight(q)<=mw,mw=weight(q);print(k","l"; "q))))
-------------------------
Output: 2,1; [-1; 1; -5]

This means that 
%F A066259 a(n) = (1/5) {F(3n+2) - (-1)^nF(n-1) }.
Also:
%F A066258 a(n) = (1/5) {F(3n+1) - (-1)^nF(n+2) }.

The solution of your original problem using these functions can now
be put together easily.
It is probably possible to express it in other terms, you just use the same
procedure with LLL.


ralf