The Ultimate Signs of Second-Order Holonomic Sequences

Abstract

A real-valued sequence $f=\{f(n){\}}_{n\in \mathbb{N}}$ is said to be second-order holonomic if it satisfies a linear recurrence $f(n+2)=P(n)f(n+1)+Q(n)f(n)$ for all sufficiently large $n$, where $P,Q\in \mathbb{R}(x)$ are rational functions. We study the ultimate sign of such a sequence, i.e., the repeated pattern that the signs of $f(n)$ follow for sufficiently large $n$. For each $P$, $Q$ we determine all the ultimate signs that $f$ can have, and show how they partition the space of initial values of $f$. This completes the prior work by Neumann, Ouaknine and Worrell, who have settled some restricted cases. As a corollary, it follows that when $P$, $Q$ have rational coefficients, $f$ either has an ultimate sign of length $1$, $2$, $3$, $4$, $6$, $8$ or $12$, or never falls into a repeated sign pattern. We also give a partial algorithm that finds the ultimate sign of $f$ (or tells that there is none) in almost all cases.

arXiv comment28 pages, 2 figures. This is a full version of the same-name paper accepted to ICALP 2025 (see related DOI). Japanese version is available at my website: https://sites.google.com/view/hagihara-fugen/%E6%97%A5%E6%9C%AC%E8%AA%9E