When is a linear recurrence relation solvable? I was reading this definition of a linear recurrence, and was wondering what characteristics are required of a linear recurrence for it to be solvable?  Meaning, can I find a closed form?
The subject of solving linear recurrence relations was just barely touched on in a Discrete Math course I took a while back, and now I'm trying to pursue the subject further as part of reading Knuth's book, Concrete Mathematics.  I've taken a Linear 1 course, but don't know anything about Linear Difference Equations.

Let's write a linear recurrence as $$f_0(n)a_n+f_1(n)a_{n-1}+\cdots+f_r(n)a_{n-r}=g(n)\tag1$$ where the functions $f_0,\dots,f_r$ and $g$ are given. 
If the $f_i$ are all constant, and $g$ is identically zero, then the solutions can be expressed in closed form in terms of the roots of the characteristic polynomial, $$f_0x^n+f_1x^{n-1}+\cdots+f_r\tag2$$ Of course, there may be no closed form for the roots of this polynomial. 
If the $f_i$ are all constant, and $g$ is of any one of a number of special forms (essentially, polynomials, exponentials, and combinations thereof), then again the solutions of (1) can be expressed in closed form in terms of the roots of (2). 
There are other special cases where (1) can be solved in closed form, but I don't think there's any kind of general theory that tells you when it can and when it can't. Click on some of the questions listed to the right under "related" to see examples done. 
