\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Manuel Kauers}
%
%
\medskip
\noindent
%
%
{\bf Shift Equivalence of P-finite Sequences}
%
%
\vskip 5mm
\noindent
%
%
%
%
We present an algorithm which decides the shift equivalence problem
for P-finite 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 shifting one of the
sequences $s$ times makes it identical to the other, for some
integer~$s$. Our algorithm computes, for any two P-finite sequences,
given via recurrence equation and initial values, all integers $s$
such that shifting the first sequence $s$ times yields the second.
\bye