There is no general way to solve all recurrence relations, however, there is a general way to solve all homogeneous linear recurrence relations exactly by employing linear algebra.
The idea is as follows: 1) For a linear recurrence relation of size $k$, e.g. $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$, write down $k$ consecutive iterations from $n-k$ to $n$.
2) Transform the set of $k$ equations into a matrix-vector form of dimension $k$. The $n$-steps of the addition of the linear recurrence combined with the $k$-dimensional vector of initial values will become a recurrence of an $n$-step $k \times k$-dimensional matrix multiplication followed by one last matrix-vector multiplication on the right side with the initial vector.
3) rewrite the $n$-step matrix multiplication of $A$ into $A^n$
4) diagonalize the matrix $A$ into three matrices: $A = TDT^{-1}$ of which $D$ is a diagonal matrix and $T$ is regular. In some corner cases, $A$ might not have a diagonalized form, in which case one should attempt to find the (more general) <PERSON> normal form of $A$ instead. 4.1) This means one need to find all eigenvalues $\Lambda$ and their corresponding eigenvectors $V$ of $A$. 4.1.1) One need to find all roots of the characteristic polynomial of $A$ to get its eigenvectors and corresponding eigenvalues.
Note that $D$ can easily be expressed in a closed form depending on $A$'s eigenvalues $\lambda_1 ... \lambda_k$, and both of $T$ and $T^{-1}$ can easily be expressed in a closed form depending on its eigenvectors $v_1 ... v_k$. At this point I would recommend to drop the parameters $c_1 ... c_k$ from the equation and abstract them away using the above $\Lambda_i$ and $v_i$ for readability.
5) now rewrite $A^n$ into $(TDT^{-1})^n = T D^n T^-1$. 945
Note that $D^n$ can easily be computed from $D$, since it is diagonal.
6) figure out an easy way to formally multiply this equation out. I recommend leaving the vector of initial values out until the very end. When finally computing $A^n * b$, note that one only need the last row of the resulting product, meaning one can leave out all others.
7) Depending on what one intend to do with the recurrence relation, it may be time to substitue $c_1 ... c_k$ back into the eigenvalues and eigenvectors.
8) The resulting equation gives $a_n$ explicitly depending only on the initial values $a_0, a_1 ... a_{k-1}$ and either $c_1, c_2 ... c_k$ or $\lambda_1 ... \lambda_k$ and $v_1 ... v_k$.
These results can be generalized for linear recurrences with affine components of n added (functions depending only on n), and even further for small polynomial, exponential and some other components depending only on n. However, it's not possible to generalize this explicit closed formula for linear recurrences for arbitrary functions depending only on n, because doing so would require a closed explicit form for arbitrary series given its sequence function, and AFAIK that's impossible.
As soon as recurrences with more than one operand are generalized from linear to polynomial recurrences, things become very complicated. Even if we allow only quadratic recurrences of a single step, things are already complicated and there are almost no non-trivial exact solutions (only a countable infinite subset out of the uncountable infinite parameter space actually do have closed forms). One neat example is $a_n = 2*a_{n-1}^2 - 1 = \cos(2^n \arccos(a_0))$, which comes from the double angle cosine law. Generally, for finding one of those sparse explicit solutions to general polynomial recurrence relations, one have to consider <PERSON> theory and keep track of repetitions, which can be done using functional properties of trigonometric or polynomials of exponential functions.
If one generalize even further, all bets are off. 945