# A Algorithms for solving recurrence relations?

1. Aug 2, 2016

### 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$.

2. Aug 2, 2016

### 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.$$

3. Aug 2, 2016

### Stephen Tashi

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$.

4. Aug 4, 2016

### 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.