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
[16]ZimingLi.ASubresultantTheoryforLinearDi erential,LinearDi erence,andOre
Polynomials,withApplications.PhDthesis,RISC-Linz,1996.
[17]ZimingLi.AsubresultanttheoryforOrepolynomialswithapplications.InProceed-
ingsofISSAC’98,pages132–139,1998.
[18]ChristianMallinger.Algorithmicmanipulationsandtransformationsofunivariate
holonomicfunctionsandsequences.Master’sthesis,J.KeplerUniversity,Linz,Au-gust1996.
[19]Yiu-KwongManandFrancisJ.Wright.Fastpolynomialdispersioncomputationand
itsapplicationtoinde nitesummation.InProceedingsofISSAC’94,pages175–180,1994.
[20]O.Ore.Theoryofnon-commutativepolynomials.AnnalsofMathematics,34:480–
508,1933.
[21]PeterPaule.Greatestfactorialfactorizationandsymbolicsummation.Journalof
SymbolicComputation,20:235–268,1995.
[22]PeterPauleandVolkerStrehl.Symbolicsummation–somerecentdevelopments.In
ComputerAlgebrainScienceandEngeneering–Algorithms,Systems,andApplica-tions,pages138–162,1995.
[23]BrunoSalvyandPaulZimmermann.Gfun:aMaplepackageforthemanipula-
tionofgeneratingandholonomicfunctionsinonevariable.ACMTransactionsonMathematicalSoftware,20(2):163–177,1994.
[24]CarstenSchneider.Acollectionofdenominatorboundstosolveparameterizedlinear
di erenceequationsinΠΣ-extensions.InProceedingsofSYNASC’04,pages269–282,2004.
[25]RichardP.Stanley.EnumerativeCombinatorics,Volume2.CambridgeStudiesin
AdvancedMathematics62.CambridgeUniversityPress,1999.
[26]DoronZeilberger.Aholonomicsystemsapproachtospecialfunctionidentities.Jour-
nalofComputationalandAppliedMathematics,32:321–368,1990.
theelectronicjournalofcombinatorics13(2006),#R0016