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