Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Finding Closed-Form Solutions of Difference Equations by Symbolic Methods

M. Petkovsek
Organization: Wolfram Research, Inc.
Journal / Anthology

Ph.D. thesis, Carnegie Mellon University
Year: 1990
Volume: CMU-CS-91-103

This thesis investigates symbolic computation in the domain of difference equations (or recurrence relations). The goal is to obtain explicit solutions of a given equation automatically and, where possible, in closed form. The main contributions of the thesis are: A comprehensive implementation of the method of generating functions as a Mathematica package called RSolve.m. The package can automatically compute ordinary and exponential generating functions for, and find closed-form solutions of, linear difference equations with constant coefficients, certain linear equations with nonconstant coefficients, equations which contain convolutions, and systems of such equations. Used as a collection of tools, the package can be employed to compute closed-form solutions of certain partial difference equations, to obtain recurrences for power-series coefficients of analytic functions, and to prove combinatorial identities. An existence and uniqueness theorem for partial difference equations in the nonnegative orthant. A proof that the generating function corresponding to the solution of a linear partial difference equation with constant coefficients with at most exponentially growing initial conditions is analytic. An algorithm for finding all polynomial solutions of a homogeneous linear difference equation with polynomial coefficients. An algorithm for finding all hypergeometric solutions of a homogeneous linear difference equation with polynomial coefficients. A sequence (hn) is hypergeometric if the quotient hn+1/hn is a rational function of n. Combined with an algorithm of Zeilberger, which, given a definite sum an= infinity k=infinity F(n,k) where F(n,k) is hypergeometric in both n and k, produces a linear recurrence for an with polynomial coefficients, it solves the long standing problem of deciding whether a definite sum such as the above is hypergeometric or not. For example, the algorithm can be used to prove that the number of involutions of an n-element set is not hypergeometric. A proof of the theorem that the Galois group of a linear difference operator with polynomial coefficients over the difference ring of germs at infinity of sequences over a field is an algebraic matrix group.

*Applied Mathematics > Numerical Methods