Vieweg Advanced Lectures in Mathematics
Wolfram Koepf
Hypergeometric Summation. An Algorithmic Approach to Summation
and Special Function Identities
1998. X, 230 pp, DM 72, $ 49, ISBN 3-528-06950-3.
Reviews: Computeralgebra-Rundbrief
23 of Fachgruppe Computeralgebra,
October 1998, pp. 27-28 (Volker Strehl);
Zbl. Math. 909.33001
(P. W. Karlsson);
Newsletter of the SIAM Activity Group on
Orthogonal Polynomials and
Special Functions 9.3, June 1999 (Tom H. Koornwinder);
MR
2000c:33002 (Jiang Zeng).
In this book modern algorithmic techniques for summation, most of which
have been introduced within the last decade, are developed and
carefully
implemented in the computer algebra system Maple.
The algorithms of Gosper, Zeilberger and Petkovsek on hypergeometric
summation and recurrence equations and their q-analogues are
covered, and similar algorithms on differential equations are
considered.
An equivalent theory of hyperexponential integration due to Almkvist
and Zeilberger completes the book.
The combination of all results considered gives work with orthogonal
polynomials and (hypergeometric type) special functions a solid
algorithmic foundation. Hence, many examples from this very active
field are given.
The present book is designed for use in the framework of a seminar but
is
also suitable for an advanced lecture course in this area.
The book's Maple software, for the generation of recurrence and
differential
equations for sums and integrals. To be loaded in Maple with
read `hsum10.mpl`;
or
read `qsum9.mpl`;
The article Algorithms for q-hypergeometric summation in computer algebra gives a description of the package qsum9.mpl. The file qsum.mws or qsum6.mws (Maple V and 6-9) is the accompanying Maple worksheet, and the Mathematica notebook qsum.nb contains some Mathematica computations from this article.
Contents:
Preface
Introduction
Chapter 1: The Gamma Function
Chapter 2: Hypergeometric Identities / q-Hypergeometric
Identities
Chapter 3: Hypergeometric Database / q-Hypergeometric
Database
Chapter 4: Holonomic Recurrence Equations / Multiple Summation / q-Holonomic
Recurrence Equations
Chapter 5: Gosper's Algorithm / Linearization of Gosper's Algorithm
/ q-Gosper Algorithm
Chapter 6: The Wilf-Zeilberger Method / q-WZ Method
Chapter 7: Zeilberger's Algorithm / q-Zeilberger Algorithm
Chapter 8: Extensions of the Algorithms
Chapter 9: Petkovsek's Algorithm / q-Petkovsek Algorithm
Chapter 10: Differential Equations for Sums / q-Differential
Equations for Sums
Chapter 11: Hyperexponential Antiderivatives
Chapter 12: Holonomic Equations for Integrals
Chapter 13: Rodrigues Formulas and Generating Functions
Appendix: Installation of the Software
Bibliography
List of Symbols
Index
Preface
The current book is the result of a lecture course that I gave at the
Free University,
Berlin, during the spring semester 1995. This course was influenced by
the
remarkable book Concrete Mathematics by Graham, Knuth and
Patashnik,
and by the interesting
lecture notes Identities and Their Computer Proofs by Herbert
Wilf.
In the meantime these notes appeared together with other
material in the book A=B by Petkovsek, Wilf and Zeilberger.
In contrast to the books just mentioned, it is my objective to present the material by giving more detailed advice on implementation. Furthermore I wished to cover not only material about recurrence equations but also about differential equations, not only about sums but also about integrals, and finally not only the hypergeometric case but also its q-analogue.
In the current book, up-to-date algorithmic techniques for summation are described in detail, and worked out using Maple programs. With Maple release V.4 and higher, some of these tools are available through Maple's sum command and sumtools package, by an implementation that I incorporated in the Maple library prior to my lecture course. In this book, readers are invited to implement the algorithms step by step. This will give them a detailed insight in the structure of the algorithms under consideration, and will enable them to solve quite involved problems.
The book covers Gosper's algorithm for indefinite hypergeometric summation and Zeilberger's algorithm for definite hypergeometric summation, as well as the WZ method and extensions of these algorithms. Petkovsek's decision procedure for hypergeometric term solutions of holonomic recurrence equations completes the picture on the summation topic.
By an analogous technique, differential equations, derivative rules and similar identities for sums can be generated, and a chapter on this topic is included. An equivalent theory of hyperexponential integration, both indefinite and definite, which was given by Almkvist and Zeilberger, completes the book.
The combination of all results considered gives work with orthogonal polynomials and (hypergeometric type) special functions a solid algorithmic foundation. Hence, many examples from this very active field are given.
Although multiple sums are briefly mentioned in Chapter 4, I have not covered the algorithmic theory of multisums, integral sums etc., which was developed by Wilf and Zeilberger. Instead, by many examples I show how the one-dimensional theory can be applied successfully to double sums and integral sums, in particular to sums and integrals involving orthogonal polynomials.
The book contains many worked examples of the algorithms considered, and Maple implementations of them are presented. Furthermore, a lot of exercises encourage the readers to do their own implementations in Maple, and to study the topics included in detail. Exercises that demand Maple implementations are marked by a diamond.
In all chapters, an introduction to the corresponding q-theory is given. Whereas in the hypergeometric case, the algorithms are rigorously presented and detailed proofs of the statements are given, in the q-case we state only the results, indicate their proofs, present Maple implementations, and give examples and exercises.
A basic knowledge of a programming language such as Pascal or C should be sufficient to understand the Maple programs and to solve the corresponding exercises since all major Maple procedures that are used are briefly described. On the other hand, a deeper familiarity with Maple might help the reader to understand the code in more detail. To obtain such a knowledge, the books [I]--[III] on p.223 might be helpful.
I could have presented the algorithms in pseudo code, without giving preference to a particular computer algebra system. On the other hand, an implementation in an existing and widely distributed computer algebra system makes the algorithms ready for execution, and therefore fills them with life. As a result, every student can execute all the examples no matter how complicated they may be.
Hence I had to decide on one of the major systems. Of the most important general purpose systems, Axiom, Macsyma, Maple, Mathematica and REDUCE, undoubtedly Maple and Mathematica have the largest audiences, since they are accessible at most universities and research institutions.
I wished to write my code as near as possible to the mathematical description of the corresponding algorithms, and since the latter depend heavily on the fast symbolic solution of (sometimes very complicated) systems of linear equations, the poor performance of Mathematica's Solve command for linear systems supported my decision to choose Maple. Furthermore Maple is much friendlier with respect to user information (e.g., the infolevel routine).
Readers who use one of these systems can access some of the algorithms considered:
Axiom: The sum command contains an implementation of Gosper's algorithm.
Macsyma: The sum command contains an implementation of Gosper's algorithm, written by Gosper.
Maple: Maple's sum command contains an implementation of Gosper's algorithm, completely rewritten by the author for Maple V.4. There are implementations of Zeilberger and Koornwinder of Zeilberger's algorithm; Almkvist and Zeilberger implemented the continuous version. Maple V.4's sumtools package was written by the author, and contains an implementation of Zeilberger's algorithm. In the present book structured implementations of Gosper's algorithm, Zeilberger's algorithm, Petkovsek's algorithm and their q-analogues are developed. Salvy and Zimmermann's Generating Functions package GFUN and Chyzak's Mgfun package are also strongly connected with the algorithms developed in the current book.
Mathematica: Implementations of Gosper's and Zeilberger's algorithms were done by Paule and Schorn, and Petkovsek implemented his algorithm and the corresponding q-version. Also Paule and Riese implemented the q-analogue of Zeilberger's algorithm. A package on multidimensional summation is due to Wegschaider.
REDUCE: Gosper's and Zeilberger's algorithms are accessible by an implementation of Koepf and Stölting. Böing and Koepf implemented the q-analogues of Gosper's and Zeilberger's algorithm.
The Maple programs for the current book are discussed in detail in the text. Some of the implementations are even printed in the book. The programs are collected in the package hsum, and can be obtained from here. Detailed information on how to download and install the software are given in an appendix on p. 214. Worksheets containing the examples given in the text, as well as Maple solutions of the exercises are available at the same URL. The corresponding q-analogues of Gosper's, Zeilberger's and Petkovsek's algorithms are implemented in the package qsum, written by Harald Böing, and can be obtained from the same site.
The present book is designed for use in the framework of a seminar. In seminars at German universities, every participating student is asked to present a lecture about a certain topic. The arrangement of the book makes the division into lectures easy. Each chapter covers a certain subtopic which can be presented by one or two students. Obviously the book is also suitable for a lecture course in this area since it was written in connection with such a course presented by the author. Special notational conventions used in the book are defined at their first occurrence, and are listed in the List of Symbols on page 224.
I would like to thank Peter Deuflhard, who introduced me to the study of this topic, for his support and encouragement. Furthermore, I thank Martin Grötschel, without whose support the final version would not have been possible. Thanks go to Herbert Melenk for his advice on Gröbner bases, and for his excellent REDUCE implementation. Due to his severe bicycling accident, a joint paper on noncommutative factorization is still unfinished. Also, I am very grateful for the warm hospitality of the ETH Zürich, where I visited to install my code in the Maple library, and especially to Mike Monagan, who headed the installation. Furthermore, thanks go to Tom Koornwinder for his implementation zeilb which was the starting point of my Maple implementations, and to Harald Böing who did some extensions of the implementations of this book that are covered in the hsum package as well as the q-implementation under my supervision. A few of the exercises have been collected by Torsten Thiele, and Lisa Temme corrected some of my English language mistakes. I am very grateful to Martin Muldoon who smoothed the English of the final manuscript and to Harald Böing for the final proofreading. Last but not least I thank Ulrike Schmickler-Hirzebruch from Vieweg as well as the editor of the current book series Martin Aigner for their good collaboration and for making this project happen.
Wolfram Koepf, April 15, 1998