Converging to Gosper’s algorithm. (English) Zbl 1173.33316
Let \(K\) be a field of characteristic zero. A nonzero term \(t_n\) is called a hypergeometric term over \(K\) if there exists a rational function, \(r\in K(n)\) such that \(t_{n+1}/t_n= r(n)\). In [Proc. Natl. Acad. Sci. USA 75, 40–42 (1978; Zbl 0384.40001)] R. W. Gosper, jun. introduced an algorithm as a procedure to find a hypergeometric term \(z_n\) satisfying \(z_{n+1}- z_n= t_n\), if it exists, or confirm the nonexistence of any solution. More generally, given a linear difference equation, S. A. Abramov has offered in [Difference equations in the field of rational functions. Analytical and numerical methods for solving problems of mathematical physics, Work Collect., Moskva, 117–121 (1989; Zbl 0728.39002)] another algorithm. The author presents a unified approach to computing the so-called universal denominators as given by Gosper’s algorithm and Abramov’s algorithm for finding rational solutions to linear difference equations with polynomial coefficients.
Reviewer: József Sándor (Cluj-Napoca)
MSC:
| 33F10 | Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) |
| 05A19 | Combinatorial identities, bijective combinatorics |
Software:
DiffToolsReferences:
| [1] | Abramov, S. A., Rational solutions of linear differential and difference equations with polynomial coefficients, USSR Comput. Maths. Math. Phys.. USSR Comput. Maths. Math. Phys., Zh. Vychisl. Mat. i Mat. Fiz., 29, 1611-1620 (1989), transl. from: · Zbl 0695.65051 |
| [2] | Abramov, S. A., Rational solutions of linear difference and \(q\)-difference equations with polynomial coefficients, (Proc. ISSAC ’95 (1995), ACM Press), 285-289 · Zbl 0914.65131 |
| [3] | Abramov, S. A.; Bronstein, M.; Petkovšek, M., On polynomial solutions of linear operator equations, (Proc. ISSAC ’95 (1995), ACM Press), 290-296 · Zbl 0914.65132 |
| [4] | Abramov, S. A.; Petkovšek, M.; Ryabenko, A., Special formal series solutions of linear operator equations, Discrete Math., 210, 3-25 (2000) · Zbl 0972.34002 |
| [5] | Barkatou, M. A., Rational solutions of matrix difference equations: The problem of equivalence and factorization, (Proc. ISSAC ’99 (1999), ACM Press), 277-282 |
| [6] | Bostan, A.; Chyzak, F.; Cluzeau, T.; Salvy, B., Low complexity algorithms for linear recurrences, (Dumas, J., Proc. ISSAC ’06 (2006), ACM Press), 31-38 · Zbl 1356.65246 |
| [7] | Gosper, R. W., Decision procedure for infinite hypergeometric summation, Proc. Natl. Acad. Sci. USA, 75, 40-42 (1978) · Zbl 0384.40001 |
| [8] | Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics—A Foundation for Computer Science (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0668.00003 |
| [9] | Koepf, W., Hypergeometric Summation (1998), Vieweg: Vieweg Braunschweig/Wiesbaden · Zbl 0909.33001 |
| [10] | Lisoněk, P.; Paule, P.; Strehl, V., Improvement of the degree setting in Gosper’s algorithm, J. Symbolic Comput., 16, 243-258 (1993) · Zbl 0872.33001 |
| [11] | Paule, P., Greatest factorial factorization and symbolic summation, J. Symbolic Comput., 20, 235-268 (1995) · Zbl 0854.68047 |
| [12] | Paule, P.; Strehl, V., Symbolic summation—some recent developments, (Fleischer, J.; Grabmeier, J.; Hehl, F.; Küchlin, W., Computer Algebra in Science and Engineering—Algorithms, Systems, and Applications (1995), World Scientific: World Scientific Singapore) |
| [13] | Petkovšek, M., Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Comput., 14, 243-264 (1992) · Zbl 0761.11008 |
| [14] | Petkovšek, M., A generalization of Gosper’s algorithm, Discrete Math., 134, 125-131 (1994) · Zbl 0813.40003 |
| [15] | Petkovšek, M.; Wilf, H. S.; Zeilberger, D., \(A = B (1996)\), AK Peters: AK Peters Wellesley, MA · Zbl 0848.05002 |
| [16] | C. Weixlbaumer, Solutions of difference equations with polynomial coefficients, Diploma thesis, RISC Linz, Johannes Kepler Universität, A-4040 Linz, Austria, 2001; C. Weixlbaumer, Solutions of difference equations with polynomial coefficients, Diploma thesis, RISC Linz, Johannes Kepler Universität, A-4040 Linz, Austria, 2001 |
| [17] | Wilf, H. S.; Zeilberger, D., An algorithmic proof theory for hypergeometric (ordinary and “\(q\)”) multisum/integral identities, Invent. Math., 108, 575-633 (1992) · Zbl 0739.05007 |
| [18] | Zeilberger, D., A holomonic systems approach to special function identities, J. Comput. Appl. Math., 32, 321-368 (1990) · Zbl 0738.33001 |
| [19] | Zeilberger, D., A fast algorithm for proving terminating identities, Discrete Math., 80, 207-211 (1990) · Zbl 0701.05001 |
| [20] | Zeilberger, D., The method of creative telescoping, J. Symbolic Comput., 11, 195-204 (1991) · Zbl 0738.33002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
