As part of a long-term project to develop an interactive system to assist with the analysis of algorithms, the authors are studying the use of generating functions to perform symbolic summation. This paper discusses certain aspects of that work. In particular, they have found these methods useful in evaluating hybrid sums, that is, sums of the form s n = ∑ a k b k.
The paper contains a brief overview of other methods (such as difference equations) for symbolic summation, including references to the work of Knuth, Karr, Moenck, and Gosper. (I would add Davis’s monograph The summation of series [1] to any bibliography for newcomers to this area.) While the applicability of the various summation methods overlaps considerably, generating functions are, as the authors show in this readable paper, an important and often complementary tool. I look forward to the implementation of their system and the development of “a comprehensive framework for the problem of symbolic summation.”