A = B by Petkovšek, Wilf, and Zeilberger

Part I Overview

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

Part I of A = B, titled "Background", sets the philosophical and mathematical stage for the algorithmic revolution in combinatorial summation. It provides the context for why computer proofs are not just possible but desirable, and defines the specific class of problems—hypergeometric identities—that the book will conquer.

1. Chapter 1: Proof Machines

The Evolution of Automated Thought

The book begins with a provocative quote from Alfred N. Whitehead: "The ultimate goal of mathematics is to eliminate any need for intelligent thought."

The Central Thesis

Chapter 1 argues that the history of mathematics is a trajectory of replacing distinct "tricks" requiring cleverness with general algorithms that require none.

• Historical Context: Just as the abacus and later calculators automated arithmetic, and computer algebra systems automated symbolic manipulation, the algorithms in this book automate the process of proving theorems in combinatorics.
• The Goal: To turn the "art" of proving identities into a "science" (or technology) where a computer can not only verify a result but generate the proof itself.

Proof vs. Verification

The chapter distinguishes between checking a proof and finding one. The methods developed in the book allow computers to discover proofs that are also succinct enough for humans to verify easily.

2. Chapter 2: Tightening the Target

Focusing on Hypergeometric Identities

After the broad philosophical introduction, Chapter 2 narrows the scope of investigation to a precise mathematical domain.

The Domain

The book focuses on hypergeometric identities. These are equations where the sum of a "huge" expression (typically involving factorials, binomial coefficients, and powers) miraculously simplifies to a compact closed form.

The Proposition

The authors promise that:

1. Computers can evaluate these sums mechanically ("no thought required").
2. Computers can produce certificates of truth (short proofs).
3. The class of problems solvable by these methods covers the vast majority of identities encountered in practice.

This chapter sets up the expectation that we are moving from ad-hoc methods to a unified theory of summation.

3. Chapter 3: The Hypergeometric Database

The Landscape of Solvable Problems

Chapter 3 formally defines the objects of study and surveys the existing landscape of known identities.

Hypergeometric Terms

A term $t_k$ is hypergeometric if the ratio of consecutive terms is a rational function of $k$: $\frac{t_{k+1}}{t_k} = \frac{P(k)}{Q(k)}$ where $P$ and $Q$ are polynomials. This includes factorials ($k!$), binomial coefficients ($\binom{n}{k}$), and powers ($2^k$), but excludes terms like $\sqrt{k!}$ or $e^{\sqrt{k}}$.

The Database

The "database" refers to the collective knowledge of proved identities in the mathematical literature (e.g., Vandermonde's Identity, Saalschütz's Identity).

• Standard Forms: The chapter discusses how essentially all "classic" summation identities involve hypergeometric terms.
• The Challenge: Before the algorthms of Part II, proving a new entry in this database was a research task. After Part II, it becomes a routine verification.

Key Takeaway

Understanding the structure of hypergeometric terms is crucial because the algorithms in Part II rely entirely on the rational nature of the term ratio $t_{k+1}/t_k$.

Synthesis: Setting the Stage

Part I serves as the motivation and definition phase of the book. It establishes:

1. Philosophy: Automation of proof is a natural mathematical evolution.
2. Scope: We restrict ourselves into the rich domain of hypergeometric sums.
3. Definitions: We rigorously define what we mean by "hypergeometric" to prepare for the algorithmic tools (Sister Celine, Gosper, Zeilberger, WZ) that follow in Part II.

Part II Overview

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.

4. 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.

5. 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.

6. 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 (Gosper'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.

7. 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$.

8. 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.

Part III Overview

Part III of A = B, titled "Epilogue", contains the final chapter of the book. It takes a step back from the specific algorithmic details of hypergeometric summation to provide a broader, more abstract algebraic perspective on the subject.

9. Chapter 9: An Operator Algebra Viewpoint

The Algebraic Structure of Summation

While the previous chapters focused on concrete algorithms (Gosper, Zeilberger, WZ) for finding recurrence relations, Chapter 9 places these methods within the rigorous framework of operator algebra.

Shifts and Operators

The chapter formalism treats sequences and functions as objects acted upon by operators:

• The Shift Operator ($E$): Defined by $E a_n = a_{n+1}$.
• The Difference Operator ($\Delta$): Defined by $\Delta = E - I$, so $\Delta a_n = a_{n+1} - a_n$.

In this framework, finding a recurrence relation for a sum amounts to finding an operator in the algebra that annihilates the sum.

The Ore Algebra

The setting for these operators is what is known as an Ore Algebra (named after Øystein Ore). It is a non-commutative polynomial ring that allows for the algebraic manipulation of linear operators such as differentiation ($D$) and shifts ($E$).

• This abstraction unifies the treatment of differential equations (continuous) and recurrence relations (discrete).
• It explains why the algorithms in Part II work: they are algorithms for elimination in specific non-commutative rings.

Connection to "A = B"

The "A = B" philosophy is shown to be a special case of the general problem of deciding if a specific element belongs to an ideal in a ring of operators. If we can prove that $A - B$ forms the kernel of an operator, or show purely algebraically that they satisfy the same defining relations, we have proven the identity.

Synthesis: The Unified Theory

Part III concludes the journey by showing that the specific "tricks" of the past and even the powerful algorithms of the present are manifestations of a deeper algebraic structure.

• From Specific to General: We moved from specific identities (Part I) to general algorithms (Part II) to abstract algebra (Part III).
• The Future: The operator viewpoint suggests how these methods can be extended beyond hypergeometric sums to q-analogs, multiple sums, and even integrals, hinting at the vast potential of computer-algebraic proof theory.