## Decision problems for second-order holonomic recurrences

*Eike Neumann*, *Joël
Ouaknine*, and *James Worrell*
We study decision problems for sequences which obey a second-order
holonomic recurrence of the form
*f*(*n*+2) = *P*(*n*)*f*(*n*+1) + *Q*(*n*)*f*(*n*) with rational polynomial coefficients, where *P* is non-constant, *Q*
is non-zero, and the degree of *Q* is smaller than or equal to that of
*P*. We show that existence of infinitely many zeroes is decidable. We
give partial algorithms for deciding the existence of a zero,
positivity of all sequence terms, and positivity of all but finitely
many sequence terms. If *Q* does not have a positive integer zero then
our algorithms halt on almost all initial values (*f*(1), *f*(2)) for the
recurrence. We identify a class of recurrences for which our
algorithms halt for all initial values. We further identify a class of
recurrences for which our algorithms can be extended to total ones.

*Proceedings of ICALP 21*, LIPIcs xxx, 2021. 20 pages.

PDF
© 2021 Eike Neumann, Joël Ouaknine, and James Worrell.

Imprint / Data Protection