How to solve homogeneous linear recurrence relations with constant coefficients? Consider a sequence $(a_n)_{n\in\mathbb N}$ defined by $k$ initial values $(a_1,\dots,a_k)$ and
$$a_{n+k}=c_{k-1}a_{n+k-1}+\dots+c_0a_n$$
for all $n\in\mathbb N$.
What are some ways to get closed forms for $a_n$? What are some ways of rewriting $a_n$ that allows it to be computed without going through all previous values?
For example, we have Binet's formula:
$$F_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}$$
Furthermore, what about simultaneously defined linear recurrences? For example:
$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$
How can these be solved?
See also: Wikipedia: Recurrence relations.

This is being repurposed in an effort to cut down on duplicates; see here:


*

*Coping with abstract duplicate questions

*List of abstract duplicates

Matrices
Such recurrences can be computed using matrices. Let $\mathbf a_n=(a_{n+k-1},\dots,a_n)^\intercal$. We can then easily see that the recurrence relation can be rewritten as
$$\mathbf a_{n+1}=C\mathbf a_n\text{ where }C=\begin{bmatrix}c_{k-1}&c_{k-2}&\cdots&c_1&c_0\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}=\begin{bmatrix}\mathbf c\\\mathbf e_0\\\mathbf e_1\\\vdots\\\mathbf e_{k-1}\end{bmatrix}$$
where $\mathbf e_i$ has a $1$ at the $i$th entry and $0$ everywhere else. See also: Companion matrix.
Intuitively we're computing the next term (top row), and then setting each entry as the one above it (a rotation of the values in $\mathbf a_n$ per se).
From this we can easily solve the recurrence, as it now becomes:
$$\mathbf a_n=C^n\mathbf a_0$$
and so the problem reduces to raising $C$ to a power. As it is the case that $C$ is diagonalizable, with eigenvalues given by the roots of the characteristic equation, a closed form can then be found. Even if the roots are not nice to compute, or if one wishes to avoid non-integers for an integer sequence, this can still be computed using exponentiation by squaring.
This also easily generalizes to simultaneously defined sequences. Consider the example:
$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$
Let $\mathbf w_n=(a_n,b_n)^\intercal$. We can then rewrite this as
$$\mathbf w_{n+1}=C\mathbf w_n\text{ where }C=\begin{bmatrix}2&1\\1&2\end{bmatrix}$$
and hence
$$\mathbf w_n=C^n\mathbf w_0$$
To show how this gives an explicit solution, we may diagonalize $C$ as
$$C=VDV^{-1}\\\text{where }D=\begin{bmatrix}1&0\\0&3\end{bmatrix},~V=\begin{bmatrix}-1&1\\1&1\end{bmatrix},~V^{-1}=\frac12V$$
and hence
$$\mathbf w_n=V\begin{bmatrix}1&0\\0&3^n\end{bmatrix}V^{-1}\mathbf w_0=\frac12\begin{bmatrix}(a_0+b_0)3^n+(a_0-b_0)\\(a_0+b_0)3^n-(a_0-b_0)\end{bmatrix}$$
which strongly suggests this specific problem can be solved by observing the behavior of $V^{-1}\mathbf w_n$ i.e. $a_n-b_n$ and $a_n+b_n$.
