Ytukyg

Generally speaking, are recurrence relations solvable into a equation, or there are some type of / some pattern of equations that are not solvable into a formula?

Say you have a recurrence relation of the form

$$a_{n+1} = sum_{k=0}^{m}c_ka_{n-k}$$

To solve this you can rewrite it into a matrix equation

$$
begin{bmatrix}
a_{n+1} \
a_{n} \
a_{n-1} \
. \
. \
a_{n-m+3} \
a_{n-m+2} \
a_{n-m+1} \
end{bmatrix}
=
begin{bmatrix}
c_0 & c_1 & c_2 & ... & c_{m-2} & c_{m-1} & c_{m} \
1 & 0 & 0 & ... & 0 & 0 & 0 \
0 & 1 & 0 & ... & 0 & 0 & 0 \
. & . & . & ... & . & . & . \
. & . & . & ... & . & . & . \
0 & 0 & 0 & ... & 0 & 0 & 0 \
0 & 0 & 0 & ... & 1 & 0 & 0 \
0 & 0 & 0 & ... & 0 & 1 & 0 \
end{bmatrix}
begin{bmatrix}
a_{n} \
a_{n-1} \
a_{n-2} \
. \
. \
a_{n-m+2} \
a_{n-m+1} \
a_{n-m} \
end{bmatrix}
$$

If we call the matrix $M$, we want to diagonalize M so it looks like $M = PDP^{-1}$, in which case $M^n = PD^nP^{-1}$. We then note that for all $n$

$$
begin{bmatrix}
a_{n} \
a_{n-1} \
a_{n-2} \
. \
. \
a_{n-m+2} \
a_{n-m+1} \
a_{n-m} \
end{bmatrix}
=
begin{bmatrix}
c_0 & c_1 & c_2 & ... & c_{m-2} & c_{m-1} & c_{m} \
1 & 0 & 0 & ... & 0 & 0 & 0 \
0 & 1 & 0 & ... & 0 & 0 & 0 \
. & . & . & ... & . & . & . \
. & . & . & ... & . & . & . \
0 & 0 & 0 & ... & 0 & 0 & 0 \
0 & 0 & 0 & ... & 1 & 0 & 0 \
0 & 0 & 0 & ... & 0 & 1 & 0 \
end{bmatrix}^{n-m}
begin{bmatrix}
a_{m} \
a_{m-1} \
a_{m-2} \
. \
. \
a_{2} \
a_{1} \
a_{0} \
end{bmatrix}
$$

So if we can get exact formulas for $P$, $D$, and $P^{-1}$ then we get get an exact formula for $M^{n-m}$ for any $n$ and thus have an exact formula for $a_n$ for any n.

Finding $P$ and $D$ is equivalent to finding the eigenvalues and eigenvectors of $M$. $M$ is square with size equal to the number of terms in the recurrence relation. If this is less than five this will be solvable as the eigenvalues are the roots of polynomial of degree less than 5. If it is five or more than it most likely has no exact solution.

So in general it is solvable into an equation if there are less than 5 terms in the recurrence relation, otherwise it is probably not.