Main Applications Identities History FAQ Algorithms

Modern algorithmic methods

Science is what we understand well enough to explain to a computer.  Art is everything else we do.
- Donald Knuth

	Are there methods for finding formulas for difficult sums of binomial coefficients?
	What is a hypergeometric series?
	What is Sister Celine’s Method?
	What is Gosper’s Algorithm?
	What is Zeilberger’s Algorithm?
	What is a WZ Proof?
	Can I get these to work with computer math packages such as Mathematica and Maple?

                       

This information on this page is a distillation of the work found in "A=B" by Petkovŝek, Wilf and Zeilberger, published by A.K. Peters, Ltd. and it is also available on-line through this link.

                 
                       

                      

                       

                       

1. Are there methods for finding formulas for difficult sums of binomial coefficients?
Yes.  While mathematicians in the past had to use their own insights and some luck to find identities in sums, in the 20th Century new methods arose that could solve whole categories of identities, not only those dealing with binomial coefficients.  Here we will discuss four of these algorithms, though not in great detail.  For more information, we recommend the book “A=B” by Petkovšek, Wilf and Zeilberger, which is available in print and on-line; the advantage of the print version is an index, which the on-line version does not include.

2. What is a hypergeometric series?
A geometric series is a sum of the form  where c is a constant; the ratio of consecutive terms cx^k and cx^k+1 is simply x.  For a hypergeometric series,  , we need t(0) = 1 and , where P and Q are polynomials in k.  Many famous series in math are hypergeometric, including Bessel functions and the polynomial sequences named for Legendre, Chebyshev, Laguerre and Hermite, among others, including the binomial coefficient summations we are chiefly interested in.  Like with integral tables used by mathematicians and engineers, there are large sets of hypergeometric series stored in lookup tables that can help solve any of a number of sums of this form; the computer program Hyp written by Krattenthaler is set up specifically for problems of this kind, and there are also ways to use the more general math programs Maple and Mathematica to solve these kinds of problems.

3. What is Sister Celine’s Method?
First published in 1945, Sister Celine’s Method is the oldest of the algorithmic methods now used and the progenitor of all those ideas that came afterwards.  It came from the doctoral thesis of Sister Mary Celine Fasenmyer, who was born in Pennsylvania in 1906.  Here are the steps.

a. Let f(n) =  F(n,k), where F(n,k) is the summand of our expression.
b. We want to find four functions, call them a(n), b(n),c(n) and d(n), that depend only on n, that satisfy this relation.

a(n)F(n,k) + b(n)F(n+1,k) + c(n)F(n,k+1) + d(n)F(n+1,k+1) = 0

If F(n,k) does not equal 0 we can divide out by it and get



c. Using linear algebra to solve for these, if we now can get a recurrence relation between terms in the sum that is free of k, we can find f(n+1) = R(n)f(n), and we can use this recurrence relation backwards down to f(1) to find a closed form free of k for f(n).

Even “simple” binomial sums can get messy using these and other algorithms, which is why computer packages are recommended when using these methods.

4. What is Gosper’s Algorithm?
With Gosper’s Algorithm, first published in 1978 by R.W. Gosper Jr., we need for the terms t(k) to be hypergeometric ; if so, we would like to find another hypergeometric term z(k) such that z(k+1)–z(k) = t(k); this would cause all the terms to telescope, and the sum would turn out to be z(n)–z(0).  For example, the sum of such a series from 0 to 5 would be

[z(6)–z(5)]+[z(5)–z(4)]+[z(4)–z(3)]+[z(3)–z(2)]+[z(2)–z(1)]+[z(1)–z(0)] =z(6)-z(0)

   Since the terms of the same color disappear or "telescope".

Given this desired outcome, here is the algorithm.

Gosper’s Algorithm
Input:  A hypergeometric term t(n)
Output: Another hypergeometric term z(n) satisfying z(n+1) – z(n) = t(n)

Step 1: Form the ratio r(n) = t(n+1)/t(n)

Step 2:   Write  , where a, b and c are polynomials that satisfy g.c.d.(a(n),b(n+h)) = 1 for non-negative integers h.

Step 3:  If it exists, find a nonzero polynomial solution x(n) to the equation a(n)x(n+1) – b(n-1)x(n) = c(n).  If it does not exist, Gosper’s Algorithm will not make any progress.

Step 4:  If Step 3 returns a useful x(n), then .
Note:  even when step 3 does not make any progress, this is still valuable information; for instance, if t(n) = n!, step 3 will say that    does not have a closed form z(n) – c, where z(n) is hypergeometric and c is a constant.


5. What is Zeilberger’s Algorithm?
Published by Doron Zeilberger in papers in 1990 and 1991, Zeilberger’s Algorithm also uses the concept of “creative telescoping”, which expands on the ideas used in both Sister Celine’s Method and Gosper’s Algorithm; like many algorithms from the “modern” era of computer science, it is concerned with speed.  [Knuth jokes that in computer science, 1970 is The Stone Age; this would mean Sister Celine, who published in 1945, was working in the Jurassic or Cretaceous Period.]  It also can find closed forms for many summations that are not Gosper summable.  (For example:  is an identity solved by Pascal himself, but because 2ⁿ is not hypergeometric, Gosper’s Algorithm would not make progress on the problem.)

Zeilberger’s Algorithm makes extensive use of difference operators such as N and K; for example, if we have a function g(n,k), Ng(n,k) = g(n+1,k), Kg(n,k) = g(n,k+1), N²g(n,k) = g(n+2,k), etc.  With creative telescoping, the partial terms that vanish might not be in neighboring terms in the original sum, but instead might be found in every other term, or every third term, etc.  This means that the step-by-step list for Zeilberger’s Algorithm isn’t quite as easy to follow, but it is effective on solving difficult summations, such as this one taken from problem 10424 from The American Mathematical Monthly.

                

The trigonometric term at the end looks peculiar, but it’s just 1, 0 or –1, depending on the value of n(mod 4).  This rather pleasant sum is the result of this seemingly recondite information returned by Zeilberger’s Algorithm:

(N²+1)(N-2)F(n,k) = (K – 1)G(n,k) where

More information can be found in Chapter 6 of “A=B”.

6. What is a WZ Proof?
Here is a quick description of the WZ proof algorithm, named for Herb Wilf and Doron Zeilberger, two of the authors of our major source text, “A=B”.

a. You have a conjecture t(n,k) = s(n), a sum in terms of a regular variable n and the summation variable k.  For any n, we also assume there are only a finite number of values of k where t(n,k) does not equal 0.
b. Divide through by the right hand side s(n), which we assume doesn’t equal zero for any n, and rename t(n,k)/s(n)=F(n,k).  This now means we want to prove F(n,k) = 1 for all n.
c. The WZ proof algorithm now provides R(n,k), a rational function, and we define G(n,k) = R(n,k)F(n,k).
d. If everything has gone according to plan, F(n+1,k)  – F(n,k) = G(n+1,k)  – G(n,k), because the right side telescopes to 0; this is equivalent to the second part of an induction proof, where we show F(n,k) = F(n+1,k), so F is independent of n.
e. Verify that F(0,k) = 1 (or whatever the first value of n is allowed to be), and we are done.

The magical work of finding the proper R(n,k), known as the WZ Certificate, is explained more fully in Chapter 7 of “A=B”.


8. Can I get these to work with computer math packages such as Mathematica and Maple?
You damn betcha.  Both Herb Wilf and Doron Zeilberger maintain links to getting software packages that work with both Maple and Mathematica.

Wilf's links

Zeilberger's links

Main Applications Identities History FAQ Algorithms