Topic #14 ------------ OP-SF NET 4.6 ------------ November 15, 1997 ~~~~~~~~~~~~~ From: Wolfram Koepf (koepf@zib.de) Subject: Review of "A = B" by Petkovsek et al. "A = B" by Marko Petkovsek, Herbert S. Wilf and Doron Zeilberger, AK Peters, Wellesley, 1996, $39.00. xii + 212 pp., ISBN 1-56881-063-6. (Editors' Note: This review is reprinted with permission from SIAM Review, Volume 39, Number 3, pages 538-540, copyright 1997 by the Society for Industrial and Applied Mathematics. It appeared in our printed Newsletter, vol 8, no 1, October 1997, pages 11-13.) In their recent research, the authors of the book under review have given important contributions towards computer proofs of hypergeometric identities. Hypergeometric identities are identites about hypergeometric sums, i.e., definite sums S_n:=sum_{k in Z} F(n,k) (1) where the summand is a hypergeometric term with respect to both n and k, i.e., the term ratios F(n+1,k)/F(n,k) and F(n,k+1)/F(n,k) are rational functions in n and k. In the book under review, this knowledge is collected, and a nice introduction to the topic is given. The main idea behind these computerized proofs is to detect a _holonomic_recurrence_equation_ for the sum S_n under consideration, i.e., a linear recurrence equation with polynomial coefficients. Zeilberger was the one having the idea how to adjust Gosper's algorithm on indefinite hypergeometric summation to the definite case. Although many of these ideas can be generalized, e.g., towards the consideration of multiple sums, integrals, q-sums, the generation of differential rather than recurrence equations, etc., the authors are mainly concerned with the above mentioned setting. The contents of the book follow: Foreword: The foreword is written by Donald Knuth. He gives some examples of sums which he was investigating, and for which the new methods are great tools. The funny thing is that his main example, S_n = sum_{k in Z} {2n-2k choose n-k}^2 {2n choose k}^2 is slightly corrupted by a typographical error. This one has a recurrence equation whose printout covers a whole page, which shows the power and the pitfalls of Zeilberger's method at the same time! The sum Knuth really meant is the much more well-behaved equation S_n = sum_{k in Z} {2n-2k choose n-k}^2 {2k choose k}^2 which satisfies the simple recurrence equation 0 = (n + 2)^3 S_{n+2} - 8(3 + 2n)(2n^2 + 6n + 5)S_{n+1} + 256(n+1)^3 S_n. Note that an errata sheet can be found at the URL http://www.cis.upenn.edu/\verb+~+wilf/AeqBErrata.html. A Quick Start...: Here, by a short example, it is shown how to download software in Maple and Mathematica from the World Wide Web, and how to deal with this software. I Background 1. Proof machines: Canonical and normal forms are discussed, and it is shown how proofs can be given ``by examples,'' using recurrence equations as normal forms. Polynomial, trigonometric, and other types of identities are discussed. 2. Tightening the target: Here the main topic of the book, the _hypergeometric_identities_, are introduced. It is shown how Mathematica and Maple deal with hypergeometric sums, and WZ proof certificates (see Chapter 7) are introduced. 3. The hypergeometric database: A database of hypergeometric identities can be used to identify sums as soon as such sums are converted into hypergeometric notation. Here this conversion is considered. II The five basic algorithms 4. Sister Celine's method: Celine Fasenmyer's method of finding a recurrence equation with respect to n for a sum S_n given by (1) is presented. Celine Fasenmyer uses linear algebra to detect a k-free recurrence equation with respect to both n and k for the _summand_, which afterwards is summed resulting in the recurrence equation searched for. 5. Gosper's algorithm: Gosper's algorithm finds a hypergeometric term antidifference s_k for a_k, i.e., s_{k+1}-s_k=a_k, whenever such an antidifference exists. As a result, indefinite summation of hypergeometric terms can be treated algorithmically. 6. Zeilberger's algorithm: Zeilberger's algorithm uses a variant of Gosper's algorithm to determine holonomic recurrence equations for definite sums, given by (1). In most cases this recurrence equation is of lowest order. If it is of first order, then one can read off the hypergeometric term solution; if it is not, Petkovsek's algorithm, described in Chapter 8, can be used to determine such solutions if applicable. Note that Zeilberger's algorithm in general is much faster than Celine Fasenmyer's method since its linear algebra part deals with mainly J+1 rather than with (J+1)^2 variables if J denotes the order of the recurrence equation searched for. 7. The WZ phenomenon: In the cases in which Zeilberger's algorithm determines a first order recurrence equation, the WZ phenomenon occurs: such a hypergeometric identity can be proved by bringing it into the form S_n:=sum_{k in Z} F(n,k) = 1 (2) and by using Gosper's algorithm to find a rational multiple G(n,k) = R(n,k) F(n,k) of F(n,k) for which F(n+1,k)-F(n,k) = G(n,k+1)-G(n,k). (3) Hence by summation, S_{n+1}-S_n = 0, proving (2) (modulo one initial value). The rational function R(n,k) is called the _WZ_proof_certificate_. Its knowledge makes a proof of (2) available by verifying a single rational identity. 8. Algorithm Hyper: Petkovsek's algorithm is a decision procedure to determine all hypergeometric term solutions of a given holonomic recurrence equation. It uses a representation lemma for rational functions initially due to Gosper, the _Gosper-Petkovsek_representation_, in a clever way. III Epilogue 9. An operator algebra viewpoint: The main theme of the book are holonomic recurrence equations. Using the shift operator N a_n:=a_{n+1}, these can also be understood as operator equations, and one can deal with them in a non-commutative algebra where the commutator rule Nn-nN=N is valid. In the given chapter this approach is considered in more detail. In the Appendix the WWW sites and the software are discussed in more detail. All algorithms that are discussed in the book under review are accompanied by examples and a few exercises for the reader, some of which come with solutions. Furthermore, the authors give examples for the use of Mathematica and Maple to do the computations. It is assumed that the reader has access to the World Wide Web or to other file transfer services, as well as to either Maple or Mathematica since the use of implementations of the algorithms considered seems to be a must. The authors refer to Maple software available from Zeilberger's WWW site, and to Mathematica software due to Krattenthaler (hypergeometric database), Paule/Schorn (Gosper's and Zeilberger's algorithms) and Petkovsek (Petkovsek's algorithm). Implementational details are not discussed. Note that the Maple package 'sumtools' written by the reviewer [2] comes with Maple V.4 and does also contain an implementation of both Gosper's and Zeilberger's algorithms. The presentation of the book is charming, and it gives an excellent introduction to this modern topic. I would like to mention two minor inconveniences, though. First, the fact that the rational certificate of an application of Zeilberger's algorithm might contain poles with some obvious defects is not addressed. Second, I find it a little inconvenient that in some instances the authors use different notations at different places of the book. This might be influenced by the fact that the book forms essentially a collection of previously published material [1], [4], [5], [6], [7]. There is no need, e.g., for new notations for rising and falling factorials different from the ones given on pages 39 and 149, respectively, in the proof of the "Fundamental Theorem" on p. 66. In my opinion, this causes confusion. Similarly, the footnote on p. 157 about the rising factorial notation is unnecessary since this definition is given on p. 39. Even worse, the mentioned footnote contains a _wrong_ notation. The authors mention the continuous analogues of the algorithms presented without giving the details. A forthcoming book by the reviewer [3] emphasizing the use of Maple for orthogonal polynomials and special functions will cover these topics. One of the highlights of the presentation is the consideration of finite sums of hypergeometric terms. The authors show how Gosper's algorithm can be extended to this case. This previously unnoticed fact is rather important since summation is a linear operation, but Gosper's original algorithm is not. REFERENCES [1] Gessel, I.M.: Finding identities with the WZ method. J. Symbolic Computation 20, 1995, 537--566. [2] Koepf, Wolfram: Summation in Maple. Maple Technical Newsletter 3 (2), 1996, 26--32. [3] Koepf, Wolfram: Hypergeometric Summation. An Algorithmic Approach to Hypergeometric Summation and Special Function Identities. Vieweg, Braunschweig/Wiesbaden, 1997, to appear. [4] Petkovsek, M.: Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symbolic Comp. 14, 1992, 243--264. [5] Wilf, H.S.: Identities and their computer proofs. "SPICE" Lecture Notes, 31 August - 2 September 1993. Previously available by anonymous ftp from ftp.cis.upenn.edu . [6] Zeilberger, D.: A fast algorithm for proving terminating hypergeometric identities. Discrete Math. 80, 1990, 207--211. [7] Zeilberger, D.: Three recitations on holonomic systems and hypergeometric series. J. Symbolic Computation 20, 1995, 699--724. Wolfram Koepf

Back to Home Page of

SIAM AG on Orthogonal Polynomials and Special Functions

Page maintained by Martin Muldoon