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

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$
