PhD Defense: Algorithms for linear recurrence sequences

In the past few decades, numerous tools for automatically discovering and proving identities involving sequences and special functions were developed. These tools are often based on algorithms which manipulate sequences satisfying linear recurrences. If the recurrences have constant coefficients, these sequences are called C-finite and in the case of polynomial coefficients they are called D-finite.

We study sequences satisfying recurrences with coefficients which are C-finite themselves and call them C^2-finite. We investigate which properties and algorithms carry over from the classical C-finite and D-finite cases to this new setting. In particular, we show that most so-called closure-properties, which are known for the classical cases, also hold for C^2-finite sequences, i.e., they are closed under termwise addition, termwise multiplication, interlacing and taking subsequences at arithmetic progressions. In many cases these operations are effective and we present algorithms for performing them. In general, however, these algorithms are closely related to and limited by certain decision procedures of C-finite sequences. Deciding whether every term of a sequence is positive or nonzero is not known to be decidable in theory. Nevertheless, we show that it is often easy to decide these properties in practice.

Restricting the ring of C^2-finite sequence to sequences which satisfy a monic (i.e., having constant leading coefficient) linear recurrence with C-finite coefficients, we obtain a subring where all closure properties can be performed effectively. On the other hand, we can allow more general sequences as coefficients. This way we obtain increasingly larger rings where the operations are more difficult to perform.

Most of the theoretical results are also implemented in a package for the computer algebra system SageMath. The thesis contains a tutorial for this package. The tutorial shows how the examples given throughout the thesis can be performed automatically on the computer.