Finding closed-form solutions of difference equations by symbolic methods

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, when possible, in closed form.;The main contributions of the thesis are: (1) 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. (2) An existence and uniqueness theorem for partial difference equations in the nonnegative orthant. (3) 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. (4) An algorithm for finding all polynomial solutions of a homogeneous linear difference equation with polynomial coefficients. (5) An algorithm for finding all hypergeometric solutions of a homogeneous linear difference equation with polynomial coefficients. A sequence (...