Tech Report CS-91-42

Generating Function Algorithms for Symbolic Computation

Robert Andrews Ravenscroft Jr.

May 1991

Abstract:

Various algebraic models have been used to implement symbolic procedures for solving summations and recurrences. Surprisingly, one model that has received little attention in the development of symbolic algorithms is generating functions. Generating function methods for discrete mathematics provide an ad hoc collection of techniques for solving summations and recurrences. In this work we consider their systematic application to symbolic computation.

To demonstrate the feasibility and capabilities of generating functions as an algebraic model of computation, we develop and implement algorithms for manipulating generating functions and the sequences that they encode. In particular, we concentrate on algorithms for solving summations and recurrences. Techniques are developed to handle special functions and hybrid terms, which are terms involving two or more factors.

Given various classes of summations and recurrences, we develop a theory to characterize the form of their solution. This allows us to demonstrate the ability of our algorithms to solve problems from these classes. This knowledge also assists us in developing algorithms that know where to look for a solution rather than doing an ad hoc search for a solution.

(complete text in pdf)