Graduate Algorithms for solving recurrence relations?

[Stephen Tashi]

Is there good survey of known algorithms for solving recurrence relations ?

By "solving" a recurrence relation such as a_n = \sum_{i=1}^{k} { c_k a_{n-k}}, I mean to express a_n as a function of n.

In the case that the c_i are constants the algorithm based on the "characteristic equation" can be used, but what is know about cases where the c_i are themselves functions of n ?

For example, it seems that the "next simplest" case would be where the c_i are known linear functions of n.

 

[pasmith]

For polynomial c_k, the trick is to multiply both sides by x^n and sum from n=0 to infinity, turning the recurrence relation into an equation of formal power series. Then you can turn that into a differential equation for f(x) = \sum a_nx^n (valid where the power series converges) by using such identities as <br /> n^kx^n = \left(x \frac{d}{dx}\right)^k x^n.

 

[Stephen Tashi]

Then you can turn that into a differential equation for f(x) = \sum a_nx^n (valid where the power series converges) by using such identities as <br /> n^kx^n = \left(x \frac{d}{dx}\right)^k x^n.

By an amusing coincidence, my interest in solving recurrence relations is prompted by the problem of solving the recurrence relations that arise in finding power series solutions to differential equations ! Common examples of that type of problem show using the D.E. to formulate the recurrence relation and then solving the recurrence relation "by inspection". So my question concerns finding a_n as an explicit function of n.

 

[pasmith]

The case <br /> a_n = (pn + q)a_{n-1} has the explicit solution <br /> a_n = a_0\prod_{k=1}^n (pk + q). This is of course just a special case of the solution of a_n = f(n)a_{n-1} being <br /> a_n = a_0\prod_{k=1}^n f(k). So where it gets difficult is <br /> a_n = (p_1n + q_1)a_{n-1} + (p_2n + q_2)a_{n-2}. However such recurrence relations are unlikely to describe coefficients of power series solutions to differential equations as they may not have strictly positive radius of convergence.