|
|
|
|
|
|
 |
|
|
Finding Closed-Form 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 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.
|
|
|
|
|
|
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
