"Algorithms for Nonlinear Higher Order Difference Equations"
, Serie RISC-Linz, 10-2005
Algorithms for Nonlinear Higher Order Difference Equations
Sprache des Titels:
In this thesis, new algorithmic methods for the treatment of special sequences are presented. The sequences that we consider are described by systems of difference equations (recurrences). These systems may be coupled, non-linear, and/or higher order. The class of sequences defined in this way (admissible sequences) contains a lot of sequences which are of interest in various mathematical applications. While some of these sequences can be handled also with known Algorithms, for many others no adequate methods were available up to now. In the center of our interest, there are algorithms for automatically proving known identities of admissible sequences, and for automatically discovering new ones. By "finding new identities", we mean in particular solving of difference equations in closed form, finding closed forms for symbolic sums, and finding algebraic dependencies of given sequences. In addition, we present a procedure by which some inequalities of admissible sequences can be proven automatically. For their algorithmic treatment, admissible sequences are represented as elements of certain special difference rings. In these difference rings, computations are then carried out, whose results can be interpreted as statements about the original admissible sequences. Known techniques for commutative multivariate polynomial rings, especially the theory of Gr\"obner bases, are applied to this end. Part of the present thesis is an implementation of the presented algorithms in form of a software package for the computer algebra system Mathematica. With the aid of our software, we succeeded in proving a lot of identities and inequalities from the literature automatically for the first time. Additionally, with the same software, we have found some identities which were probably unknown up to now.