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.

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