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
 A: Characteristic/Auxiliary Polynomials
The basic solution


*

*Suppose that $\alpha$ is a root of the associated polynomial $$x^k=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_0\quad(1)$$ Then it is also true that $$\alpha^{n+k}=c_1\alpha^{n+k-1}+\dots+c_0\alpha^n$$ So $a_n=\alpha^n$ satisfies the recurrence relation (but probably not the initial conditions). 

*Since the relation is linear, if $\alpha_1,\alpha_2,\dots,\alpha_k$ are the roots of the associated polynomial, then $$a_n=A_1\alpha_1^n+\dots+A_k\alpha_k^n$$ also satisfies the recurrence relation. Provided all $k$ roots are distinct, we can then use the $k$ initial conditions to solve for $A_1,\dots,A_k$. 

*Suppose that $\alpha$ is a repeated root. Then $\alpha$ is also a root of the derivative and so we have $$kx^{k-1}=c_{k-1}(k-1)x^{k-2}+\dots+c_0\quad(2)$$ Taking $nx^n(1)+x^{n+1}(2)$ we get $$(n+k)x^{n+k}=c_{k-1}(n+k-1)x^{n+k-1}+\dots+c_0nx^n$$ and so $a_n=n\alpha^n$ is satisfies the recurrence relation.

*Similarly, we find that if $\alpha$ is a root of order $h$ (so that $(x-\alpha)^h$ divides the polynomial, then $a_n=\alpha^n,n\alpha^n,n^2\alpha^n,\dots,n^{h-1}\alpha^n$ all satisfy the recurrence relation.

*So in all cases the associated polynomial gives us $k$ solutions to the recurrence relation. We then take a suitable linear combination of those solutions to satisfy the initial conditions.
Additional points


*If often happens that all but one of the roots $\alpha$ of the polynomial satisfy $|\alpha|<1$ which means that their contribution to $a_n$ is negligible except possibly for small $n$. Since the $a_n$ are usually integers, this means we can often express the solution as $\lfloor A\alpha^n\rfloor$ or $\lceil A\alpha^n\rceil$ (where $\alpha$ is the root with $|\alpha|>1$.

*We sometimes get simultaneous linear recurrences like the two in the question $$a_{n+1}=2a_n+b_n,b_{n+1}=a_n+2b_n$$ In this case we can eliminate all but one of the sequences, in a similar way to solving ordinary simultaneous equations. In this case we have $b_n=a_{n+1}-2a_n$. Substituting in the other relation; $a_{n+2}-2a_{n+1}=a_n+2a_{n+1}-4a_n$
A: 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$.
A: Generating functions / Z-transforms
Generating functions (unilateral Z-transforms) can be used to transform the recurrence into a formal power series by defining:
$$G=\sum_{n=0}^\infty a_nx^n$$
We can then rearrange this to get
$$G=\sum_{n=0}^{k-1}a_nx^n+G\sum_{n=1}^kc_{k-n}x^{n-1}$$
Solving for $G$ then gives a rational function in $x$. By factoring the denominator (which equates to solving the characteristic equation), applying partial fractions, and using the geometric series or Newton's generalized binomial theorem, the general term in the expansion of $G$ can be computed. Alternatively, by using Taylor's series, we know that
$$a_n=\frac{G^{(n)}(0)}{n!}$$
which can be computed directly by differentiating repeatedly, using Leibniz's rule for example.
Example:
The Fibonacci sequence can be solved this way. Recall that $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$. Now let us take
$$G=\sum_{n=0}^\infty F_nx^n$$
By algebraic manipulation,
$$G=x+(x+x^2)G$$
$$G=\frac x{1-x-x^2}$$
For multiple simultaneously defined sequences, this simply amounts to multiple generating functions, which when solving amounts interestingly to solving a system of equations of functions. After that the rest is the same as above.
