The factorial-basis method for finding definite-sum solutions of linear recurrences with polynomial coefficients

(infinity)(k=0) The problem of finding a nonzero solution of a linear recurrence Ly = 0 with polynomial coefficients where y has the form of a def-inite hypergeometric sum, related to the Inverse Creative Telescop-ing 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)(infinity) of the polynomial space K[n] over a field K of characteristic zero, com-putes a recurrence satisfied by the coefficient sequence c = < c(k)>(infinity)(k=0) of the solution y(n) = Sigma(infinity)(k=0)c(k)P(k)(n) (where, thanks to the quasi -triangularity of L3, the sum on the right terminates for each n is an element of N). More generally, if B is m-sieved for some m is an element of 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 Ly = 0. (C) 2022 Elsevier Ltd. All rights reserved.