Simple $C^2$-finite Sequences: a Computable Generalization of $C$-finite Sequences

The class of $C^2$-finite sequences is a natural generalization of holonomic sequences and consists of sequences satisfying a linear recurrence with C-finite coefficients, i.e., coefficients satisfying a linear recurrence with constant coefficients themselves. Recently, we investigated computational properties of $C^2$-finite sequences: we showed that these sequences form a difference ring and provided methods to compute in this ring. From an algorithmic point of view, some of these results were not as far reaching as we hoped for. In this paper, we define the class of simple $C^2$-finite sequences and show that it satisfies the same computational properties, but does not share the same technical issues. In particular, we are able to derive bounds for the asymptotic behavior, can compute closure properties more efficiently, and have a characterization via the generating function.