request for help with obscure sequence

Tue Jul 15 12:10:08 CEST 2008

Dear Richard and other seqfans, 

The exact formula for the terms d_n of A122046, which are the degrees of the polynomials 
generated by the quadratic recurrence 

P_{n}P_{n-5}= x^{n-1}P_{n-1}P_{n-4}+P_{n-2}P{n-3} -----(*)

with the five initial values P_{-3}=...=P_1=1, is 

d_n =\frac{1/4\sqrt{2}}\cos((2n+1)\pi / 4)+\frac{1}{96}(2n+3)(2n^2+6n-5)+\frac{1}{32}(-1)^n. 

This comes from the fact that the degrees d_n satisfy the 7th order homogeneous linear recurrence 

(S-1)^4(S+1)(S^2+1)d_n=0 

(where S is the shift operator, i.e. Sf_n =f_{n+1}) and the seven initial values for this are 
d_{-3}=...=d_1=0 and d_2=1,d_3=3. 

The proof is as follows: 

Assume that (*) with five initial 1s generates a sequence of polynomials in x (see note below). 

Then from (*) it follows that the degrees of the polynomials satisfy the 5th order recurrence 

d_{n}+d_{n-5} = max \{ n-1 + d_{n-1}+d_{n-4},d_{n-2}+d_{n-3} \} 

(with 5 zeros as initial data: d_{-3}=...=d_1=0). 

Letting v_n =  d_n+d_{n-3}-d_{n-1}-d_{n-2} this becomes the second order recurrence 

v_n+v_{n-2}=\max { n-1, - v_{n-1} \}   ---(**)  

with initial values v_0=v_1=0. By induction it is easy to see that v_n is non-negative and 
satisfies 

v_n + v_{n-2} = n-1 

for all n \geq 2 (so the first term on the r.h.s. of (**)  is always the largest). 
This is equivalent to a 5th order linear inhomogeneous recurrence for the degrees 
d_n (whose consequence is the 7th order homogeneous linear recurrence given above), 
and the explicit formula for d_n then follows. 

Note: Richard Mathar has alerted me to the fact that apparently no proof has been given that the 
recurrence (*) introduced by Roger Bagula does indeed produce polynomials in x. The recurrence (*) is a non-autonomous version of the Somos-5 recurrence, and the fact that it generates 
polynomials is a generalisation of the Laurent phenomenon studied by Fomin & Zelevisnky in 
their work on cluster algebras. However, their methods to not apply directly here. Nevertheless, 
I think it is fairly easy to prove the Laurent property for (*) directly by induction - when I 
have time I will supply a proof to anyone that is interested. I'm currently writing a book on 
nonlinear recurrences, in which the OEIS is likely to feature, and there should be a chapter 
on these type of recurrences which are related to discrete Painleve equations.

Lastly,  I've noticed that A122047 should say "Somos-6" not "Samos-6". The proof 
of the Laurent property for the quadratic recurrence appearing in A122047 is likely to be rather 
harder, and will require a fair amount of computer algebra. 

All the best
Andy 

P.S. I'll put my old poster, relevant to A014125,A122046,A122047 up on the arXiv 
later this week, so that the broken link can be removed. There are some errors in the poster 
(including a conjecture which is certainly wrong) but I am inclined to upload it in its original 
form rather than succumb to revisionism. 

----- Original Message -----
From: A.N.W.Hone at kent.ac.uk
Date: Monday, July 14, 2008 10:24 am
Subject: Re: request for help with obscrure sequence
To: Richard Mathar <mathar at strw.leidenuniv.nl>
Cc: seqfan at ext.jussieu.fr

> Hi seqfans,  
> 
> That looks like the right definition of the sequence, which 
> perhaps the author (Roger Bagula) 
> can confirm. 
> 
> I'd be very surprised if there is not a simple exact formuala 
> for the degrees - let me have a look 
> at it. 
> 
> I'll try to restore the broken link to my preprint this week, 
> but I see that there is a cached copy. 
> Maybe I'll just put it on the arXiv, if it's not there already. 
> 
> Andy 
> 
> 
> ----- Original Message -----
> From: Richard Mathar <mathar at strw.leidenuniv.nl>
> Date: Friday, July 11, 2008 8:09 pm
> Subject: Re: request for help with obscrure sequence
> To: seqfan at ext.jussieu.fr
> 
> > 
> > njas> From seqfan-owner at ext.jussieu.fr  Fri Jul 11 
> 14:48:15 2008
> > njas> Date: Fri, 11 Jul 2008 08:46:52 -0400
> > njas> From: "N. J. A. Sloane" <njas at research.att.com>
> > njas> To: seqfan at ext.jussieu.fr
> > njas> Subject: request for help with obscrure sequence
> > njas> Cc: jerry_metzger at und.nodak.edu, njas at research.att.com
> > njas> 
> > njas> Dear Seqfans,  can someone figure out what the 
> > definition means?
> > njas> The link is broken, and A N W Hone has not responded to
> > njas> my asking for a new URL for the article.
> > njas> Neil
> > njas> ...
> > njas> %S A122046 
> > 
> 0,0,1,3,6,10,16,24,34,46,61,79,100,124,152,184,220,260,305,355,410njas> %N A122046 a(n)=(x^(n - 1)a(n - 1)a(n - 4) + a(n - 2)*a(n - 3))/a(n - 5).
> > njas> %F A122046 Comment from Jerry Metzger 
> > (jerry_metzger(AT)und.nodak.edu), Jul 09 2008: It appears that 
> > every 4th term is given by Sum_{m=1...n-1} (floor{m(n-2)/n})^2 
> > and the intermediate terms by adding an easy "adjustment" term 
> > to that sum.
> > njas> ...
> > 
> > The definition is
> > Degree of the polynomial P(n,x)= [x^(n-1)*P(n-1,x)*P(n-
> 4,x)+P(n-
> > 2,x)*P(n-3,x)]/P(n-5,x) with P(1,x)=P(0,x)=P(-1,x)=P(-2,x)=P(-
> 3,x)=1.> 
> > The sequence continues
> > 0, 0, 1, 3, 6, 10, 16, 24, 34, 46, 61, 79, 100, 124, 152, 184, 
> > 220, 260, 305,
> > 355, 410, 470, 536, 608, 686, 770, 861, 959, 1064, 1176, 1296, 
> > 1424, 1560, 1704,
> > 1857, 2019, 2190, 2370, 2560
> > 
> > found with a Maple program
> > 
> > P := proc(n) option remember ;
> >         if n <= 1 then
> >                 RETURN(1) ;
> >         else
> >                 (P(n-1)*P(n-4)*q^(n-1)+P(n-2)*P(n-3))/P(n-5) ;
> >                 expand(%) ;
> >                 factor(%) ;
> >         fi ;
> > end:
> > for n from 0 to 80 do
> >         bag := P(n) ;
> >         printf("%d 
> > %d\n",n,degree(bag,q)) ;
> > od:
> > 
> > It does not satisfy a linear recurrence with 6 or less 
> > coefficients (as
> > one may have hoped spying at A014125).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080715/4bbef9d9/attachment-0001.htm>