The factorial-basis method for finding definite-sum solutions of linear recurrences with polynomial coefficients. (July 2023)

• Record Type: Journal Article
• Authors: Jiménez-Pastor, Antonio; Petkovšek, Marko
• Is Part Of: Journal of symbolic computation. Volume 117(2023)
• Page Start: 15
• Page End: 50
• Publication Date: 2023-07
• Subjects: 33F10 -- 39A06 -- 68W30; Definite hypergeometric sums -- Shift-compatible factorial bases -- (Formal) polynomial series -- Quasi-triangular bases -- Binomial-coefficient bases -- Solutions of linear recurrences; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.11.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: The problem of finding a nonzero solution of a linear recurrence L y = 0 with polynomial coefficients where y has the form of a definite hypergeometric sum, related to the Inverse Creative Telescoping Problem of Chen and Kauers (2017, Sec. 8), has now been open for three decades. Here we present an algorithm (implemented in a SageMath package) which, given such a recurrence and a quasi-triangular, shift-compatible factorial basis B = 〈 P k ( n ) 〉 k = 0 ∞ of the polynomial space K [ n ] over a field K of characteristic zero, computes a recurrence satisfied by the coefficient sequence c = 〈 c k 〉 k = 0 ∞ of the solution y n = ∑ k = 0 ∞ c k P k ( n ) (where, thanks to the quasi-triangularity of B, the sum on the right terminates for each n ∈ N ). More generally, if B is m -sieved for some m ∈ N, our algorithm computes a system of m recurrences satisfied by the m -sections of the coefficient sequence c . If an explicit nonzero solution of this system can be found, we obtain an explicit nonzero solution of L y = 0 .