Some MACSYMA program for solving difference equations

A set of MACSYMA programs are described for finding closed form solutions to linear recurrence relations in equations having either constant or variable coefficients. In the homogenous case, a polymonial equation is obtained and the solution to the recurrence relation can be written as a linear combination of the roots of the polynomial. Exponential generating functions are used to solve variable coefficient relations. Taking successive derivatives and using the recurrence relation, an ordinary differential equation is obtained. Expanding the solution to the differential equation in a Taylor series, shows that the nth term of the series is the solution to the recurrence relation. For second order recurrences, a check is made for those that can be solved in terms of Bessel functions.