Effective Bounds for P-Recursive Sequences

Abstract

We describe an algorithm that takes as input a complex sequence $(u_n)$ given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound $(v_n)$ such that $|u_n|\le v_n$ for all $n$. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of $u_n$. We discuss applications to the evaluation of power series with guaranteed precision.

26 pages

Cited by in corpus (10)

• Multiple binomial sums
• An Accurate Numerical Method and Algorithm for Constructing Solutions of Chaotic Systems
• Confluence of meromorphic solutions of q-difference equations
• Kostant's partition function and magic multiplex juggling sequences
• Bernstein-Type Bounds for Beta Distribution
• Rounding Error Analysis of Linear Recurrences Using Generating Series
• A Note on the Space Complexity of Fast D-Finite Function Evaluation
• D-finite Numbers
• When can we decide that a P-finite sequence is positive?
• NumGfun: a Package for Numerical and Analytic Computation with D-finite Functions