








Finding ClosedForm Solutions of Difference Equations by Symbolic Methods






Organization:  Wolfram Research, Inc. 






Ph.D. thesis, Carnegie Mellon University 






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 closedform 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 closedform solutions of certain partial difference equations, to obtain recurrences for powerseries 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 nelement 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.













     
