The factorial-basis method for finding definite-sum solutions of linear recurrences with polynomial coefficients
العنوان: | The factorial-basis method for finding definite-sum solutions of linear recurrences with polynomial coefficients |
---|---|
المؤلفون: | Jiménez-Pastor, Antonio, Petkovšek, Marko |
المصدر: | Journal of Symbolic Computation. 117:15-50 |
بيانات النشر: | Elsevier BV, 2023. |
سنة النشر: | 2023 |
مصطلحات موضوعية: | FOS: Computer and information sciences, Computer Science - Symbolic Computation, 33F10, 39A06, 68W30, Computational Mathematics, Algebra and Number Theory, Computer Science - Mathematical Software, Symbolic Computation (cs.SC), Mathematical Software (cs.MS) |
الوصف: | The problem of finding a nonzero solution of a linear recurrence $Ly = 0$ with polynomial coefficients where $y$ has the form of a definite hypergeometric sum, related to the Inverse Creative Telescoping Problem of [14][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 $\mathcal{B} = \langle P_k(n)\rangle_{k=0}^\infty$ of the polynomial space $\mathbb{K}[n]$ over a field $\mathbb{K}$ of characteristic zero, computes a recurrence satisfied by the coefficient sequence $c = \langle c_k\rangle_{k=0}^\infty$ of the solution $y_n = \sum_{k=0}^\infty c_kP_k(n)$ (where, thanks to the quasi-triangularity of $\mathcal{B}$, the sum on the right terminates for each $n \in \mathbb{N}$). More generally, if $\mathcal{B}$ is $m$-sieved for some $m \in \mathbb{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$. 62 pages |
تدمد: | 0747-7171 |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6c0e672c98838e755cdc0a31c2adc0e1 https://doi.org/10.1016/j.jsc.2022.11.002 |
حقوق: | OPEN |
رقم الأكسشن: | edsair.doi.dedup.....6c0e672c98838e755cdc0a31c2adc0e1 |
قاعدة البيانات: | OpenAIRE |
تدمد: | 07477171 |
---|