We present an algorithm which decides the shift equivalence problem for Pfinite sequences. A sequence is called P-finite if it satisfies a homogeneous linear recurrence equation with polynomial coefficients. Two sequences are called shift equivalent if shi
ShiftEquivalenceofP- niteSequences
ManuelKauers
ResearchInstituteforSymbolicComputation
JohannesKeplerUniversity
Altenbergerstraße69
A4040Linz,Austria
mkauers@risc.uni-linz.ac.at
Submitted:Aug8,2006;Accepted:Oct19,2006
MathematicsSubjectClassi cation:68W30
Abstract
WepresentanalgorithmwhichdecidestheshiftequivalenceproblemforP- nitesequences.AsequenceiscalledP- niteifitsatis esahomogeneouslinearrecurrenceequationwithpolynomialcoe cients.Twosequencesarecalledshiftequivalentifshiftingoneofthesequencesstimesmakesitidenticaltotheother,forsomeintegers.Ouralgorithmcomputes,foranytwoP- nitesequences,givenviarecurrenceequationandinitialvalues,allintegersssuchthatshiftingthe rstsequencestimesyieldsthesecond.
1Introduction
Thispaperispartofalong-termprojectconcerningthedevelopmentofasymbolicsum-mationalgorithmfor ndingclosedformsofsums
n k=1rat(n,f1(n),...,fr(n)),
wheref1(n),...,fr(n)satisfyhomogeneouslinearrecurrenceequationswithpolynomialcoe cientsandratisamultivariaterationalfunction.Theprincipalquestionistodecidewhetherthereexistsanotherrationalfunctionrat1suchthattheabovesumisequaltorat1(n,f1(n),...,fr(n))forn≥1,andifso,tocomputeone.
Alreadythecasewherethefi(n)satisfylinearrecurrenceequationswithconstantcoe cientsisunsolved.Inarecentpaper,GreeneandWilf[13]haveprovidedapartial