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.
 A: 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. 
A: Consider a sequence $a_0, a_1, \dotsc$ with a finite linear recurrence with constant coefficients: $a_n = \sum_{i = 1}^mk_ia_{n - i}$ for some constant $m$. Let $v_j = \begin{bmatrix}a_{j - 1} & a_{j - 2} & \cdots & a_{j - m}\end{bmatrix}^\intercal$ for any $j > m$, where $v_m$ is known. Then we have
$$
v_{j + 1} = \overbrace{\begin{bmatrix}k_1 & k_2 & \cdots & k_{m - 1} & k_m\\1 & 0 & \cdots & 0 & 0\\0 & 1 & \cdots & 0 & 0\\\vdots & \vdots & \ddots & \vdots & \vdots\\0 & 0 & \cdots & 1 & 0\end{bmatrix}}^Mv_j.
$$
In the event that we can diagonalize $M = P^{-1}\operatorname{diag}(d_1, d_2, \dotsc, d_m)P$,
$$
(Pv_{m + j}) = \begin{bmatrix}d_1^j & 0 & \cdots & 0\\0 & d_2^j & \cdots & 0\\\vdots & \vdots & \ddots & \vdots\\0 & 0 & \cdots & d_m^j\end{bmatrix}(Pv_m).
$$
This should give a closed form for the sequence $a_0, a_1, \dotsc$.
A: One of the cases that can always be "solved" is the linear recurrence of first order:
$$
a_{n + 1} = f(n) a_n + g(n)
$$
Divide by the summing factor $s_n = \prod_{0 \le k \le n} f(k)$ to get:
$$
\frac{a_{n + 1}}{s_n} - \frac{a_n}{s_{n - 1}} = \frac{g(n)}{s_n}
$$
Sum for $n$ from 0 to $n$, the right hand side telescopes:
$$
\frac{a_{n + 1}}{s_n}
  = a_0 + \sum_{0 \le k \le n} \frac{g(k)}{s_k}
$$
This obviously requires $s_k \ne 0$ for the relevant range(i.e., $f(k) \ne 0$), and it qualifies as a "solution" as long as you know the left hand side's sum and $s_n$ has a nice form.
Most linear recurrences of higher orders can't be solved in closed form (just like the case for differential equations, there are uncanny parallels). In some cases defining a generating function (see e.g. Wilf's "generatingfunctionology", the next to last edition is available for free at the link) gets you an algebraic or differential equation that can be solved, in which case you get the terms as the coefficients of the solution. For linear recurrences with constant coefficients generating functions offer a clean, general way to solve them. Some nonlinear recurrences also succumb to this approach.
