The Automatic Solution of Recurrence Relations. {I}. {Linear} Recurrences of Finite Order with Constant Coefficients

Publication TypeMiscellaneous
Year of Publication2003
AuthorsBagnara R, Zaccagnini A, Zolo T
Keywordscomplexity analysis, recurrence relations, software verification, static analysis

We describe algorithmic techniques for the efficient solution of a wide class of linear recurrences of finite order with constant coefficients. We give an outline of the underlying theory both from an abstract and a more concrete point of view, in an attempt to convey the general principles as clearly as possible yet providing a well marked path for the implementation. In particular, the presentation is thorough and reasonably self-contained, covering topics such as the automatic solution of polynomial equations and efficient, exact symbolic summation of some special functions.

We are a passionate team of experts. Do not hesitate to let us have your feedback:
You may be surprised to discover just how much your suggestions matter to us.