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
WehaveL·f1=L·f2=0for
L=E3+E2 E 1=(E+1)(E 1)2∈k[E].
ComputingtheJordandecompositionofthecompanionmatrix,we nd
010
C:= 001 111 1 1001/4 1/21/41/4 1/21/4
= 1/41/23/4 011 1/41/23/4 =:T 1JT.
001 1/201/2 1/201/2
ApplyingTtothevectorsofinitialvaluesleadsto
018 1
u¯=T 0 = 3 ,v¯=T 8 = 5 .
424 2
Itremainsto nds∈suchthat
s 11 100 3 = 011 5 .
22001
ThematrixJconsistsoftwoJordanblockswhichhavetobeconsideredseparately.The rstblockhaslength1,anditrestrictsthesolutionstotheset
S1:={s∈:1
2 ( 5