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
5Letr:=deg(L)andC∈kbethecompanionmatrixofLreturn
,f2(1)=4
Inoperatornotation,wehave
(E3 5E2+8E 4)·f1=0, =:L174.
Thegreatestcommondivisoroftheseoperatorsis(E3 2E2 4E+8)·f2=0. =:L2
L:=gcd(L1,L2)=E2 4E+4=(E 2)2,
anditcanbecheckedthatL·f1=L·f2=0.
ComputingtheJordandecompositionofthecompanionmatrix,we nd
1 01/2210101/2=:T 1JT.··=C:=02 21 44 21
ApplyingTtothevectorsofinitialvaluesleadsto
01/20 801/21/47/32u¯==,v¯==. 21 16 16 217/16 1/16
Itremainstodetermines∈suchthat s 8217/32=. 1602 1/16
8 (2)SinceJconsistsofasingleJordanblockofsizetwo,wehaveauniquesolutioncandidate:
s=2 1/16=8
Indeed,(2)isfull lledfors=8,anditfollowsthatf1=Esf2ifandonlyifs=8.Example2Considerf1,f2:→de nedvia
f1(0)=0,f1(1)=0,f1(2)=4,
f2(0)=8,f2(1)=8,f2(2)=4.
10f1(n+3)= f1(n+2)+f1(n+1)+f1(n),f2(n+3)= f2(n+2)+f2(n+1)+f2(n),theelectronicjournalofcombinatorics13(2006),#R00