Skip to main content

2013 | OriginalPaper | Buchkapitel

Solving Linear Recurrence Equations with Polynomial Coefficients

verfasst von : Marko Petkovšek, Helena Zakrajšek

Erschienen in: Computer Algebra in Quantum Field Theory

Verlag: Springer Vienna

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Summation is closely related to solving linear recurrence equations, since an indefinite sum satisfies a first-order linear recurrence with constant coefficients, and a definite proper-hypergeometric sum satisfies a linear recurrence with polynomial coefficients. Conversely, d’Alembertian solutions of linear recurrences can be expressed as nested indefinite sums with hypergeometric summands. We sketch the simplest algorithms for finding polynomial, rational, hypergeometric, d’Alembertian, and Liouvillian solutions of linear recurrences with polynomial coefficients, and refer to the relevant literature for state-of-the-art algorithms for these tasks. We outline an algorithm for finding the minimal annihilator of a given P-recursive sequence, prove the salient closure properties of d’Alembertian sequences, and present an alternative proof of a recent result of Reutenauer’s that Liouvillian sequences are precisely the interlacings of d’Alembertian ones.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
C-recursive sequences are also called linear recurrent (or: recurrence) sequences. This neglects sequences satisfying linear recurrences with non-constant coefficients, and may lead to confusion.
 
2
A hypergeometric sequence is also called a hypergeometric term, because the nth term of a hypergeometric series, considered as a function of n, is a hypergeometric sequence in our sense.
 
Literatur
1.
Zurück zum Zitat Ablinger, J., Blümlein, J., Schneider, C.: Harmonic sums and polylogarithms generated by cyclotomic polynomials. J. Math. Phys. 52, 1–52 (2011)CrossRef Ablinger, J., Blümlein, J., Schneider, C.: Harmonic sums and polylogarithms generated by cyclotomic polynomials. J. Math. Phys. 52, 1–52 (2011)CrossRef
2.
Zurück zum Zitat Ablinger, J., Blümlein, J., Schneider, C.: Analytic and algorithmic aspects of generalized harmonic sums and polylogarithms. J. Math. Phys. (2013, to appear) Ablinger, J., Blümlein, J., Schneider, C.: Analytic and algorithmic aspects of generalized harmonic sums and polylogarithms. J. Math. Phys. (2013, to appear)
3.
Zurück zum Zitat Abramov, S.A.: Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations. Moscow Univ. Comput. Math. Cybern. 3, 63–68 (1989). Transl. from Vestn. Moskov. univ. Ser. XV. Vychisl. mat. kibernet. 3, 56–60 (1989) Abramov, S.A.: Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations. Moscow Univ. Comput. Math. Cybern. 3, 63–68 (1989). Transl. from Vestn. Moskov. univ. Ser. XV. Vychisl. mat. kibernet. 3, 56–60 (1989)
4.
Zurück zum Zitat Abramov, S.A.: Rational solutions of linear differential and difference equations with polynomial coefficients. U.S.S.R. Comput. Maths. Math. Phys. 29, 7–12 (1989). Transl. from Zh. vychisl. mat. mat. fyz. 29, 1611–1620 (1989) Abramov, S.A.: Rational solutions of linear differential and difference equations with polynomial coefficients. U.S.S.R. Comput. Maths. Math. Phys. 29, 7–12 (1989). Transl. from Zh. vychisl. mat. mat. fyz. 29, 1611–1620 (1989)
5.
Zurück zum Zitat Abramov, S.A.: On d’Alembert substitution. In: Proceedings of the ISSAC’93, Kiev, pp. 20–26 (1993) Abramov, S.A.: On d’Alembert substitution. In: Proceedings of the ISSAC’93, Kiev, pp. 20–26 (1993)
6.
Zurück zum Zitat Abramov, S.A.: Rational solutions of linear difference and q-difference equations with polynomial coefficients. Progr. Comput. Softw. 21, 273–278 (1995). Transl. from Programmirovanie 21, 3–11 (1995) Abramov, S.A.: Rational solutions of linear difference and q-difference equations with polynomial coefficients. Progr. Comput. Softw. 21, 273–278 (1995). Transl. from Programmirovanie 21, 3–11 (1995)
7.
Zurück zum Zitat Abramov, S.A., Barkatou, M.A.: Rational solutions of first order linear difference systems. In: Proceedings of the ISSAC’98, Rostock, pp. 124–131 (1998) Abramov, S.A., Barkatou, M.A.: Rational solutions of first order linear difference systems. In: Proceedings of the ISSAC’98, Rostock, pp. 124–131 (1998)
8.
Zurück zum Zitat Abramov, S.A., Barkatou, M.A., Khmelnov, D.E.: On m-interlacing solutions of linear difference equations. In: Proceedings of the CASC’09, Kobe. LNCS 5743, pp. 1–17. Springer, Berlin/Heidelberg/New York (2009) Abramov, S.A., Barkatou, M.A., Khmelnov, D.E.: On m-interlacing solutions of linear difference equations. In: Proceedings of the CASC’09, Kobe. LNCS 5743, pp. 1–17. Springer, Berlin/Heidelberg/New York (2009)
9.
Zurück zum Zitat Abramov, S.A., Bronstein, M., Petkovšek, M.: On polynomial solutions of linear operator equations. In: Proceedings of the ISSAC’95, Montreal, pp. 290–296 (1995) Abramov, S.A., Bronstein, M., Petkovšek, M.: On polynomial solutions of linear operator equations. In: Proceedings of the ISSAC’95, Montreal, pp. 290–296 (1995)
10.
Zurück zum Zitat Abramov, S.A., Petkovšek, M.: D’Alembertian solutions of linear operator equations. In: Proceedings of the ISSAC’94, Oxford, pp. 169–174 (1994) Abramov, S.A., Petkovšek, M.: D’Alembertian solutions of linear operator equations. In: Proceedings of the ISSAC’94, Oxford, pp. 169–174 (1994)
11.
Zurück zum Zitat Apagodu, M., Zeilberger, D.: Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory. Adv. Appl. Math. 37, 139–152 (2006)MathSciNetCrossRefMATH Apagodu, M., Zeilberger, D.: Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory. Adv. Appl. Math. 37, 139–152 (2006)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Blümlein, J., Klein, S., Schneider, C., Stan, F.: A symbolic summation approach to Feynman integral calculus. J. Symb. Comput. 47, 1267–1289 (2012)CrossRefMATH Blümlein, J., Klein, S., Schneider, C., Stan, F.: A symbolic summation approach to Feynman integral calculus. J. Symb. Comput. 47, 1267–1289 (2012)CrossRefMATH
13.
Zurück zum Zitat Bomboy, R.: Liouvillian solutions of ordinary linear difference equations. In: Proceedings of the CASC’02, Simeiz (Yalta), pp. 17–28 (2002) Bomboy, R.: Liouvillian solutions of ordinary linear difference equations. In: Proceedings of the CASC’02, Simeiz (Yalta), pp. 17–28 (2002)
14.
Zurück zum Zitat Bronstein, M., Petkovšek, M.: Ore rings, linear operators and factorization. Progr. Comput. Softw. 20, 14–26 (1994) Bronstein, M., Petkovšek, M.: Ore rings, linear operators and factorization. Progr. Comput. Softw. 20, 14–26 (1994)
15.
16.
Zurück zum Zitat Cha, Y., van Hoeij, M.: Liouvillian solutions of irreducible linear difference equations. In: Proceedings of the ISSAC’09, Seoul, pp. 87–94 (2009) Cha, Y., van Hoeij, M.: Liouvillian solutions of irreducible linear difference equations. In: Proceedings of the ISSAC’09, Seoul, pp. 87–94 (2009)
17.
Zurück zum Zitat Cha, Y., van Hoeij, M., Levy, G.: Solving recurrence relations using local invariants. In: Proceedings of the ISSAC’10, München, pp. 303–309 (2010) Cha, Y., van Hoeij, M., Levy, G.: Solving recurrence relations using local invariants. In: Proceedings of the ISSAC’10, München, pp. 303–309 (2010)
18.
Zurück zum Zitat Cluzeau, T., van Hoeij, M.: Computing hypergeometric solutions of linear recurrence equations. Appl. Algebra Eng. Comm. Comput. 17, 83–115 (2006)CrossRefMATH Cluzeau, T., van Hoeij, M.: Computing hypergeometric solutions of linear recurrence equations. Appl. Algebra Eng. Comm. Comput. 17, 83–115 (2006)CrossRefMATH
19.
Zurück zum Zitat Cohn, R.M.: Difference Algebra. Interscience Publishers/Wiley, New York/London/Sydney (1965)MATH Cohn, R.M.: Difference Algebra. Interscience Publishers/Wiley, New York/London/Sydney (1965)MATH
20.
Zurück zum Zitat Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Padé approximations to the logarithm. II. Identities, recurrences, and symbolic computation. Ramanujan J. 11, 139–158 (2006) Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Padé approximations to the logarithm. II. Identities, recurrences, and symbolic computation. Ramanujan J. 11, 139–158 (2006)
21.
Zurück zum Zitat Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Padé approximations to the logarithm. III. Alternative methods and additional results, Ramanujan J. 12, 299–314 (2006) Driver, K., Prodinger, H., Schneider, C., Weideman, J.A.C.: Padé approximations to the logarithm. III. Alternative methods and additional results, Ramanujan J. 12, 299–314 (2006)
22.
Zurück zum Zitat Feng, R., Singer, M.F., Wu, M.: Liouvillian solutions of linear difference-differential equations. J. Symb. Comput. 45, 287–305 (2010)MathSciNetCrossRefMATH Feng, R., Singer, M.F., Wu, M.: Liouvillian solutions of linear difference-differential equations. J. Symb. Comput. 45, 287–305 (2010)MathSciNetCrossRefMATH
23.
Zurück zum Zitat Feng, R., Singer, M.F., Wu, M.: An algorithm to compute Liouvillian solutions of prime order linear difference-differential equations. J. Symb. Comput. 45, 306–323 (2010)MathSciNetCrossRefMATH Feng, R., Singer, M.F., Wu, M.: An algorithm to compute Liouvillian solutions of prime order linear difference-differential equations. J. Symb. Comput. 45, 306–323 (2010)MathSciNetCrossRefMATH
24.
25.
Zurück zum Zitat Khmelnov, D.E.: Search for Liouvillian solutions of linear recurrence equations in MAPLE computer algebra system. Progr. Comput. Softw. 34, 204–209 (2008)MathSciNetCrossRefMATH Khmelnov, D.E.: Search for Liouvillian solutions of linear recurrence equations in MAPLE computer algebra system. Progr. Comput. Softw. 34, 204–209 (2008)MathSciNetCrossRefMATH
26.
Zurück zum Zitat Larson, R.G., Taft, E.J.: The algebraic structure of linearly recursive sequences under Hadamard product. Israel J. Math. 72, 118–132 (1990)MathSciNetCrossRefMATH Larson, R.G., Taft, E.J.: The algebraic structure of linearly recursive sequences under Hadamard product. Israel J. Math. 72, 118–132 (1990)MathSciNetCrossRefMATH
27.
Zurück zum Zitat Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities. Adv. Appl. Math. 31, 359–378 (2003)MathSciNetCrossRefMATH Paule, P., Schneider, C.: Computer proofs of a new family of harmonic number identities. Adv. Appl. Math. 31, 359–378 (2003)MathSciNetCrossRefMATH
28.
Zurück zum Zitat Petkovšek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symb. Comput. 14, 243–264 (1992)CrossRefMATH Petkovšek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symb. Comput. 14, 243–264 (1992)CrossRefMATH
29.
Zurück zum Zitat Petkovšek, M., Wilf, H.S., Zeilberger, D.: A =B. A K Peters, Wellesley (1996) Petkovšek, M., Wilf, H.S., Zeilberger, D.: A =B. A K Peters, Wellesley (1996)
30.
Zurück zum Zitat Reutenauer, C.: On a matrix representation for polynomially recursive sequences. Electron. J. Combin. 19(3), P36 (2012)MathSciNet Reutenauer, C.: On a matrix representation for polynomially recursive sequences. Electron. J. Combin. 19(3), P36 (2012)MathSciNet
31.
Zurück zum Zitat Schneider, C.: The summation package Sigma: underlying principles and a rhombus tiling application. Discret. Math. Theor. Comput. Sci. 6, 365–386 (2004). (electronic) Schneider, C.: The summation package Sigma: underlying principles and a rhombus tiling application. Discret. Math. Theor. Comput. Sci. 6, 365–386 (2004). (electronic)
32.
Zurück zum Zitat Schneider, C.: Solving parameterized linear difference equations in terms of indefinite nested sums and products. J. Differ. Equ. Appl. 11, 799–821 (2005)CrossRefMATH Schneider, C.: Solving parameterized linear difference equations in terms of indefinite nested sums and products. J. Differ. Equ. Appl. 11, 799–821 (2005)CrossRefMATH
33.
Zurück zum Zitat Schneider, C.: Symbolic summation assists combinatorics. Sém. Lothar. Combin. 56 (2006/07). Art. B56b (electronic), 36 pp Schneider, C.: Symbolic summation assists combinatorics. Sém. Lothar. Combin. 56 (2006/07). Art. B56b (electronic), 36 pp
35.
Zurück zum Zitat Schneider, C.: A refined difference field theory for symbolic summation. J. Symb. Comput. 43, 611–644 (2008)CrossRefMATH Schneider, C.: A refined difference field theory for symbolic summation. J. Symb. Comput. 43, 611–644 (2008)CrossRefMATH
36.
Zurück zum Zitat Schneider, C.: Structural theorems for symbolic summation. Appl. Algebra Eng. Comm. Comput. 21, 1–32 (2010)CrossRefMATH Schneider, C.: Structural theorems for symbolic summation. Appl. Algebra Eng. Comm. Comput. 21, 1–32 (2010)CrossRefMATH
38.
Zurück zum Zitat Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (1997) (corrected reprint of the 1986 original)CrossRefMATH Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (1997) (corrected reprint of the 1986 original)CrossRefMATH
39.
Zurück zum Zitat Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)CrossRef Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)CrossRef
40.
Zurück zum Zitat van der Put, M., Singer, M.F.: Galois Theory of Difference Equations. Springer, Berlin (1997)MATH van der Put, M., Singer, M.F.: Galois Theory of Difference Equations. Springer, Berlin (1997)MATH
41.
Zurück zum Zitat van Hoeij, M.: Rational solutions of linear difference equations. In: Proceedings of the ISSAC’98, Rostock, pp. 120–123 (1998) van Hoeij, M.: Rational solutions of linear difference equations. In: Proceedings of the ISSAC’98, Rostock, pp. 120–123 (1998)
42.
Zurück zum Zitat van Hoeij, M.: Finite singularities and hypergeometric solutions of linear recurrence equations. J. Pure Appl. Algebra 139, 109–131 (1999)MathSciNetCrossRefMATH van Hoeij, M.: Finite singularities and hypergeometric solutions of linear recurrence equations. J. Pure Appl. Algebra 139, 109–131 (1999)MathSciNetCrossRefMATH
43.
Zurück zum Zitat van Hoeij, M., Levy, G.: Liouvillian solutions of irreducible second order linear differential equations. In: Proceedings of the ISSAC’10, München, pp. 297–301 (2010) van Hoeij, M., Levy, G.: Liouvillian solutions of irreducible second order linear differential equations. In: Proceedings of the ISSAC’10, München, pp. 297–301 (2010)
44.
Metadaten
Titel
Solving Linear Recurrence Equations with Polynomial Coefficients
verfasst von
Marko Petkovšek
Helena Zakrajšek
Copyright-Jahr
2013
Verlag
Springer Vienna
DOI
https://doi.org/10.1007/978-3-7091-1616-6_11