A = B: The Five Basic Algorithms for Computerized Identity Proofs

Part II Overview

Based on the book "A = B" by Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger.

Part II of A = B, titled "The Five Basic Algorithms", constitutes the core of the book's treatment of computerized closed-form summation and proofs of hypergeometric identities. It transitions from manual techniques to fully automated algorithmic methods that revolutionized combinatorial mathematics.

The section details five key algorithms that allow computers to discover and prove identities that essentially state "A = B". These algorithms form a pipeline for handling hypergeometric sums, moving from existence proofs to practical implementation and finally to generating "certificates" of truth.

1. Chapter 4: Sister Celine’s Method

The Historical Foundation

Sister Mary Celine Fasenmyer (1945) developed the first systematic algorithmic method for finding recurrence relations for hypergeometric sums.

The Problem

Given a sum $f(n) = \sum_k F(n, k)$, we wish to find a recurrence relation satisfied by $f(n)$.

The Method

Sister Celine's method proceeds by finding a recurrence for the summand $F(n, k)$ itself. Because $F(n, k)$ is hypergeometric, it satisfies a linear recurrence relation with polynomial coefficients of the form: $\sum_{i=0}^I \sum_{j=0}^J a_{i,j}(n) F(n+i, k+j) = 0$ By summing this relation over $k$, one can derive a recurrence for $f(n)$.

Significance

While Sister Celine's method is often computationally slow due to the large system of linear equations it generates, it provided the existence theorems guaranteeing that such recurrences exist for a broad class of hypergeometric terms. It paved the way for more efficient algorithms.

2. Chapter 5: Gosper’s Algorithm

Indefinite Summation

R.W. Gosper (1978) provided a definitive algorithm for the problem of indefinite summation of hypergeometric terms.

The Question

Given a hypergeometric term $t_k$, does there exist another hypergeometric term $z_k$ such that: $z_{k+1} - z_k = t_k$ If yes, then $\sum_{k=a}^b t_k = z_{b+1} - z_a$.

The Algorithm

Gosper's algorithm is a decision procedure:

1. It determines whether such a $z_k$ exists.
2. If it returns "Success", it constructs $z_k$.
3. If it returns "Failure", it proves that no such hypergeometric $z_k$ exists.

This is analogous to determining if a function has an elementary antiderivative in calculus (Risch algorithm), but for discrete summation. Gosper's algorithm is a critical subroutine for the more advanced algorithms in subsequent chapters.

3. Chapter 6: Zeilberger’s Algorithm

Creative Telescoping

Doron Zeilberger extended the concepts of Sister Celine and Gosper to create a powerful method for definite sums, often called "Creative Telescoping".

The Innovation

Instead of finding a recurrence for the sum directly (as in Celine's method) or summing indefinitely (Groper's), Zeilberger's algorithm looks for a recurrence for the summand $F(n, k)$ of a specific form: $\sum_{j=0}^J a_j(n) F(n+j, k) = G(n, k+1) - G(n, k)$ where $G(n, k)$ is a hypergeometric term (modulo factors).

The Process

The algorithm uses Gosper's algorithm to determine the coefficients $a_j(n)$ and the function $G(n,k)$. Summing both sides over $k$ makes the right hand side telescope to zero (under natural boundary conditions), leaving a homogeneous recurrence for the sum $f(n) = \sum_k F(n, k)$: $\sum_{j=0}^J a_j(n) f(n+j) = 0$ This method is significantly faster than Sister Celine's and is the standard workhorse for modern symbolic summation.

4. Chapter 7: The WZ Phenomenon

Proof by Certification

Wilf and Zeilberger (1990) introduced a stunningly concise way to certify identities, known as WZ theory.

The Certificate

To prove an identity involving a sum, the WZ method provides a single rational function $R(n, k)$ as a certificate. An identity $\sum_k F(n, k) = \text{const}$ is proved by verifying a relationship of the form: $F(n+1, k) - F(n, k) = G(n, k+1) - G(n, k)$ where $G(n, k) = R(n, k)F(n, k)$.

Key Features

• Conciseness: A proof that might take pages of manual manipulation is reduced to checking a rational function.
• Duality: The symmetry in WZ pairs $(F, G)$ often implies new, sometimes unexpected, "dual" identities by swapping the roles of $n$ and $k$.

5. Chapter 8: Algorithm Hyper

Solving Recurrences

While Zeilberger's algorithm finds a recurrence relation for a sum, it does not solve it. Marko Petkovšek (1992) developed Algorithm Hyper to close the loop.

The Problem

Given a linear recurrence relation with polynomial coefficients: $\sum_{i=0}^d p_i(n) y(n+i) = 0$ Find all "closed form" solutions, specifically those where $y(n)$ is a linear combination of hypergeometric terms.

The Solution

Algorithm Hyper finds all hypergeometric solutions or proves that none exist. When combined with Zeilberger's algorithm, this provides a complete decision procedure for the closed-form evaluation of hypergeometric sums:

1. Zeilberger: Find the recurrence.
2. Hyper: Solve the recurrence.

If Hyper finds no solution, then the sum cannot be expressed as a linear combination of a fixed number of hypergeometric terms.

Synthesis: The Z-P Route

Part II establishes what is often called the Zeilberger-Petkovšek (Z-P) route for "doing" a sum:

1. Input: A definite sum $f(n) = \sum_k F(n, k)$.
2. Step 1 (Zeilberger): Use the method of Chapter 6 (Creative Telescoping) to find a recurrence relation satisfied by $f(n)$.
3. Step 2 (Hyper): Use the algorithm of Chapter 8 to solve this recurrence for $f(n)$ in terms of hypergeometric functions.
4. Result: A closed-form expression for the sum, or a proof that none exists.