FAMP and recurrence relations

[Creighton Dement]

Dear Seqfans, 

An important asset of FAMP, in my opinion, is that if you can find a
sequence (a(n)) (say, "vesseq") it will tell you which sequences are its
"most important companions" ("jesseq", "tesseq", ...). This, however,
comes at a small price: let's say we know of a sequence satisfying some
linear recurrence relation and, naturally, would like to know what its
"favorite companions" are, for ex.:

http://www.research.att.com/projects/OEIS?Anum=A002530
Denominators of continued fraction convergents to sqrt(3).   
a(n)=4a(n-2)+a(n-4)

I have searched for this sequence for a long time with FAMP with no
luck- though I would be very surprised 
it it wasn't there *somewhere*. Without a database of documented
generating functions corresponding to 
floretions parametrized in one way or another (or some unknown theorem),
there is no way I know of to simply write down 
a floretion which will generate, say, a sequence having the desired
recurrence relation with a given set of initial values. This is
certainly one area I wish I had outside help with because otherwise it
is a very slow process.   

One thing is almost definitely for sure: if X is a floretion and F =
{'i, 'j, ..., 'ii', 'jj', ...} is the set of basis vectors and if
there exists a natural number m such that m*tesseq[X] (or ibaseseq, or
jbaseseq, ...) = m*(coeff. of unit in X, coeff. of unit in X^2, coeff.
of unit in X^3, ...) = (a(n)) is an integer sequence, then (a(n)) has a
rational generating function.   

To continue, Fib/Pell numbers were found within the first few weeks of
experimentation (there are many ways to generate these numbers). In
contrast, it took much longer to find the floretion + .5'i + .5i' +
.5'ik' + .5'ji' + .5'jk' + .5'kj' corresponding to the Perrin sequence
(=4kbasejseq[X], a(n) = a(n-2) + a(n-3)). Once that was found, however,
I immediately knew its "good friend" was the Padovan sequence
(=4tesseq[X]).  Another sequence I am pleased to have recently had the
(complete) luck to find is: "denominators of continued fraction
convergents to sqrt(12)", FAMP Code: teszapseq[A*L*cyc(A)] with A =  +
.5'i - .5'k + .5i' - .5k' - 'jj' - .5'ij' - .5'ji' - .5'jk' - .5'kj' ; L
=  + .5'i + .5i' + .5'jj' + .5'kk' and "cyc(A)" being the floretion
formed by taking A and replacing i with j, j with k, k with i.  A
similar relation gives: "denominators of continued fraction convergents
to sqrt(20)". 

I consider this to be important: given any 2nd order recurrence relation
a(n) = c*a(n-1) + d*a(n-2) it appears that it will soon be possible to
pull up a batch of sequences satisfying that relation. This is something
that I've never really felt was close to happening until today. 

Define the following A =  + .25'i + .25i' + .25'ii' + .25'jj' + .25'kk'
+ .25'jk' + .25'kj' + .25e  and
L_m =  + 'i + i' + 'ik' + 'ji' + 'jk' + 'kj' + m*e

Comment from Henry Bottomley:
In general sequences with recurrence a(n)=(2k+1)*a(n-1)+a(n-2) and      
        a(0)=1 [and a(-1)=0] have generating function 1/(1-kx-x^2). If k
is               odd they satisfy a(3n)=b(5n), a(3n+1)=b(5n+3),
a(3n+2)=2*b(5n+4)              where b(n) is the sequence of
denominators of continued fraction               convergents to
sqrt(k^2+4). [If k is even then a(n) is the sequence of              
denominators of continued fraction convergents to sqrt(k^2/4+1).]

**********
   
We have:
2tesseq[A*L_0]: 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1basejseq[A*L_0]: 0, 0, 0, 0, 0, 0, 0, 0, 0

4tesseq[A*L_1]: 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199  //Lucas
2basejseq[A*L_1]: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144  //Fib 
g.f. den x^2-1+x

2tesseq[A*L_2]: 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363
// numerators ... sqrt(2)
1basejseq[A*L_2]: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985 
//  denominators ... sqrt(2) g.f. den x^2-1+2*x

4tesseq[A*L_3]: 3, 11, 36, 119, 393, 1298, 4287, 14159, 46764
 // A006497
2basejseq[A*L_3]: 0, 3, 9, 30, 99, 327, 1080, 3567, // A052906
2ibasekseq[A*L_3]: 1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837
// denominators ... (3+Sqrt[13])/2. g.f. den x^2-1+3*x

2tesseq[A*L_4]: 2, 9, 38, 161, 682, 2889, 12238, 51841
// numerators ... sqrt(5)
1jbasejseq[A*L_4]: 1, 4, 17, 72, 305, 1292, 5473, 23184
// denominators ... sqrt(5) g.f. den x^2-1+4*x

4tesseq[A*L_5]: 5, 27, 140, 727, 3775, 19602, 101785 // A087130
2jbaseseq[A*L_5]: -1, -5, -26, -135, -701, -3640, -18901 // A052918
( Note: if we introduce a cyclic transform similar to the one described,
above, we get:
4baseicycseq[A*L_5]: 5, -1, -4, -21, -109, -566, -2939, -15261 //
A100237, throw out initial term )

2tesseq[A*L_6]: 3, 19, 117, 721, 4443, 27379, 168717, 1039681
// numerators ... sqrt(10) 
2jbaseseq[A*L_6]: -1, -6, -37, -228, -1405, -8658, -53353
// denominators ... sqrt(10) x^2-1+6*x
 

The relation between A*L_m and x^2-1+m*x is clear. Define L(a,b,m) = 
+ a'i + bi' + 'ik' + 'ji' + 'jk' + 'kj' + me. Then, 

2tesseq[A*L(2,3,1)]: -1, 6, -16, 56, -176, 576, -1856, 6016 // A084057
without signs, g.f. den. 4x^2-1-2x

2tesseq[A*L(2,3,2)]: -1, 15, -22, 127, -281, 1170, -3137, 11327, -33286
// g.f. den 7*x^2-1-x

1tesseq[A*L(2,3,3)]: 0, 5, 0, 50, 0, 500, 0, 5000, 0, 50000, 0, 500000,
0, 5000000 // g.f. den 10*x^2-1

4tesseq[A*L(2,3,4)]: 1, 27, 40, 391, 911, 5994, 17837, 95759, 327640
// g.f. den 13*x^2-1+x

We are apparently increasing the coeffiecient of x^2 by 3 and the
coefficient of x by 1 in going from L(2,3,m) to L(2,3,m+1). As you can
see, there is still work to be done. If all goes well, I will have some
general formula mapped out within the next few days. Of course, the next
step is to continue the procedure with 3rd order recurrence relations. 

Sincerely, 
Creighton