FAMP and recurrence relations

[Creighton Dement]

 - - - - - - - - - - - - - - - - - - - - - - - - - - - -

> Date: Wed,  3 Aug 2005 14:46:09 +0200
> Subject: FAMP and recurrence relations
> From: "Creighton Dement" <crowdog at crowdog.de>
> To: seqfan at ext.jussieu.fr

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


After a several months of on and off (unsystematic) searching, I finally
found http://www.research.att.com/projects/OEIS?Anum=A002531
Numerators of continued fraction convergents to sqrt(3).

The (or better: A) formula is 1em[I]seq[A*B] with A =  + .25'i + .25i' +
'ij' + .25'jk' + .25'kj' and
B =  + j' + k' + 'ii' 

An alternative formula is: 1famtesseq[A*B]: 1, -2, -5, 7, 19, -26, -71,
97, 265
 
Two of its "close companions" are: 

4basejseq: -1, 2, 5, -8, -19, 30, 71, -112, -265, 418, 989, -1560
http://www.research.att.com/projects/OEIS?Anum=A082630
Name: Start with the sequence S(0)={1,1} and for n>0 define S(n) to be
I(S(n-1)) where I denotes the operation of inserting, for i=1,2,3...,   
           the term a(i)+a(i+1) between any two terms for which
7a(i+1)<=11a(i). The listed terms are the initial terms of the limit of
this process.

 and  
     
1fam*seq: -1, 0, 1, -1, -3, 4, 11, -15, -41, 56, 153, -209, -571, 780
Denominators of continued fraction convergents to sqrt(3). 

 and
 
1tesseq: 0, -2, 0, 7, 0, -26, 0, 97, 0, -362, 0, 1351, 0, -5042
(Upon bisecting:) Chebyshev's T(n,x) polynomials evaluated at x=2.


In addition, we have 1vesseq[A*B]:  0, 0, -4, -1, 16, 4, -60, -15, 224,
56, -836, -209, 3120, 780

Note that the bisections here are
http://www.research.att.com/projects/OEIS?Anum=A001353
"3*a(n)^2 + 1 is a perfect square" and 4*A001353.


The identity fam + fam* = ves holds, thus 
fam + tes + fam* = famtes + fam* = ves + tes. So,  
(1, -2, -5, 7, 19, -26, -71, 97,) + (-1, 0, 1, -1, -3, 4, 11, -15, -41,)
=  
(0, 0, -4, -1, 16, 4, -60, -15,) + (0, -2, 0, 7, 0, -26, 0, 97, 0, -362)


I'm currenctly trying to document the g.f.'s associated with various
floretions on my site http://www.crowdog.de/20801/46618.html
(note: the page is still under construction and the top link has not
been filled)
 
The main conjecture given there is: 

Conjecture III (Main): Let a(n) = c1*a(n-1) + c2*a(n-2) + c3*a(n-3) +
c4*a(n-4) be a homogeneous linear recurrence relation of order 1 (
c2=c3=c3=0), 2 (c3=c4=0), 3 (c4=0), or 4 with constant coefficients.
Then there exists an element X in B such that tesseq(X) also satisfies
the same recurrence relation (or, if (a(n)) has a rational generating
function P(x)/Q(X) where Q = 1 - c1*x - c2*x^2 - c3*x^3 - c4*x^4 then an
X in B exists such that the den. of the g.f. of tesseq(X) is Q).

Actually, I assume the above conjecture is overly optimistic and that
some - perhaps many- recurrences will be left out in the end. That said,
I've already seen enough to know that it's a conjecture worth making at
this point, i.e. a proof or contradiction needs to be found.

Note: I may post some variant of this message to sci.math, soon. 
 
Sincerely, 
Creighton