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 $$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 $$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 $$a_n = (pn + q)a_{n-1}$$ has the explicit solution $$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 $$a_n = a_0\prod_{k=1}^n f(k).$$ So where it gets difficult is $$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.