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