Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

m-Fold Hypergeometric Solutions of Linear Recurrence Equations Revisited

  • Published:
Mathematics in Computer Science Aims and scope Submit manuscript

Abstract

We present two algorithms to compute m-fold hypergeometric solutions of linear recurrence equations for the classical shift case and for the q-case, respectively. The first is an m-fold generalization and q-generalization of the algorithm by van Hoeij (Appl Algebra Eng Commun Comput 17:83–115, 2005; J. Pure Appl Algebra 139:109–131, 1998) for recurrence equations. The second is a combination of an improved version of the algorithms by Petkovšek (Discrete Math 180:3–22, 1998; J Symb Comput 14(2–3):243–264, 1992) for recurrence and q-recurrence equations and the m-fold algorithm from Petkovšek and Salvy (ISSAC 1993 Proceedings, pp 27–33, 1993) for recurrence equations. We will refer to the classical algorithms as van Hoeij or Petkovšek respectively. To formulate our ideas, we first need to introduce an adapted version of an m-fold Newton polygon and its characteristic polynomials for the classical case and q-case, and to prove the important properties in this case. Using the data from the Newton polygon, we are able to present efficient m-fold versions of the van Hoeij and Petkovšek algorithms for the classical shift case and for the q-case, respectively. Furthermore, we show how one can use the Newton polygon and our characteristic polynomials to conclude for which \({m\in \mathbb{N}}\) there might be an m-fold hypergeometric solution at all. Again by using the information obtained from the Newton polygon, the presentation of the q-Petkovšek algorithm can be simplified and streamlined. Finally, we give timings for the ‘classical’ q-Petkovšek, our q-van Hoeij and our modified q-Petkovšek algorithm on some classes of problems and we present a Maple implementation of the m-fold algorithms for the q-case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abramov, S.: Rational solutions to linear difference and q-difference equations with polynomial coefficients. Programmirovanie (6), 3–11 (1995)

  2. Abramov, S., Bronstein, M., Petkovšek, M.: On polynomial solutions of linear operator equations. In: ISSAC 1995 Proceedings, pp. 290–296 (1995)

  3. Abramov S., Paule P., Petkovšek M.: q-Hypergeometric solutions of q-difference equations. Discrete Math. 180, 3–22 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Böing H., Koepf W.: Algorithms for q-hypergeometric summation in computer algebra. J. Symb. Comput. 28, 777–799 (1999)

    Article  MATH  Google Scholar 

  5. Cluzeau T., van Hoeij M.: Computing hypergeometric solutions of linear recurrence equations. Appl. Algebra Eng. Commun. Comput. 17, 83–115 (2005)

    Article  Google Scholar 

  6. Duval A.: Lemmes de Hensel et Factorisation Formelle pour les Opérateurs aux Différences. Funkcialaj Ekvacioj 26, 349–368 (1983)

    MathSciNet  MATH  Google Scholar 

  7. Hendriks P.A., Singer M.F.: Solving difference equations in finite terms. J. Symb. Comput. 27, 239–259 (1998)

    Article  MathSciNet  Google Scholar 

  8. Horn, P.: Faktorisierung in Schief-Polynomringen. PhD thesis, Universität Kassel (2008)

  9. Petkovšek M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symb. Comput. 14(2–3), 243–264 (1992)

    Article  MATH  Google Scholar 

  10. Petkovšek, M., Salvy, B.: Finding all hypergeometric solutions of linear differential equations. In: ISSAC 1993 Proceedings, pp. 27–33 (1993)

  11. Robba P.: Lemmes de Hensel pour les opérateurs différentiels. Application à la réduction formelle des équations différentielles. L’Enseignement Mathématique 26(3–4), 279–311 (1980)

    MathSciNet  MATH  Google Scholar 

  12. Sprenger, T., Koepf, W.: Algorithmic determination of q-power series for q-holonomic functions. J. Symb. Comput. (2011). doi:10.1016/j.jsc.2011.12.004

  13. van Hoeij M.: Finite singularities and hypergeometric solutions of linear recurrence equations. J. Pure Appl. Algebra 139, 109–131 (1998)

    Article  Google Scholar 

  14. van Hoeij, M.: Rational solutions of linear difference equations. In: ISSAC 1998 Proceedings, pp. 120–123 (1998)

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, University of Kassel, 34132, Kassel, Germany

    Peter Horn, Wolfram Koepf & Torsten Sprenger

Authors
  1. Peter Horn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wolfram Koepf
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Torsten Sprenger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wolfram Koepf.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Horn, P., Koepf, W. & Sprenger, T. m-Fold Hypergeometric Solutions of Linear Recurrence Equations Revisited. Math.Comput.Sci. 6, 61–77 (2012). https://doi.org/10.1007/s11786-012-0107-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11786-012-0107-8

Keywords

Mathematics Subject Classification (2000)

Search

Navigation