A method for finding Recurrence Relations for hypergeometric polynomials directly from the
series expansions of the polynomials. The method is effective and easily implemented, but usually slower than
Zeilberger's Algorithm. Given a sum
, the method operates by finding a recurrence of the form

by proceeding as follows (Petkovsek

- 1. Fix trial values of and .
- 2. Assume a recurrence formula of the above form where are to be solved for.
- 3. Divide each term of the assumed recurrence by and reduce every ratio by simplifying the ratios of its constituent factorials so that only Rational Functions in and remain.
- 4. Put the resulting expression over a common Denominator, then collect the numerator as a Polynomial in .
- 5. Solve the system of linear equations that results after setting the coefficients of each power of in the Numerator to 0 for the unknown coefficients .
- 6. If no solution results, start again with larger or .

**References**

Fasenmyer, Sister M. C. *Some Generalized Hypergeometric Polynomials.* Ph.D. thesis. University of Michigan, Nov. 1945.

Fasenmyer, Sister M. C. ``Some Generalized Hypergeometric Polynomials.'' *Bull. Amer. Math. Soc.* **53**, 806-812, 1947.

Fasenmyer, Sister M. C. ``A Note on Pure Recurrence Relations.'' *Amer. Math. Monthly* **56**, 14-17, 1949.

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. ``Sister Celine's Method.'' Ch. 4 in *A=B.*
Wellesley, MA: A. K. Peters, pp. 55-72, 1996.

Rainville, E. D. Chs. 14 and 18 in *Special Functions.* New York: Chelsea, 1971.

Verbaten, P. ``The Automatic Construction of Pure Recurrence Relations.'' *Proc. EUROSAM '74, ACM-SIGSAM Bull.* **8**, 96-98,
1974.

Wilf, H. S. and Zeilberger, D. ``An Algorithmic Proof Theory for Hypergeometric (Ordinary and ``'') Multisum/Integral Identities.''
*Invent. Math.* **108**, 575-633, 1992.

© 1996-9

1999-05-26