Shift Equivalence of P-finite Sequences

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Shift Equivalence of P-finite Sequences在线全文阅读。