Find the general solution of the recurrence relation.
$a_n = 4a_{n – 1} – 5a_{n – 2} + 4a_{n – 3} – 4a_{n – 4}$
I've found the roots, but I don't really understand how does general solution look like.
$$r^n = 4r^{n – 1} – 5r^{n – 2} + 4r^{n – 3} – 4r^{n – 4} \iff r^4 – 4r^3 + 5r^2 – 4r + 4 = 0 \iff (r – 2)^2(r^2 + 1) = 0$$
$$\begin{cases}
r = 2\\
r = i\\
r = -i
\end{cases}$$
So far, I've only studied how to solve linear recurrences of second order(homogeneous/non-homogeneous) and I know there are three cases that depend whether the root is complex or not.
If we have two complex roots the solution has the following form: $$a_n = c_1p^n\cos(nv) + c_2p^n(\sin nv)$$
($v$ is an argument of $r_1, r_2$, $p$ also comes from exponentiation form of $r_1$, $r_2$)
Two real roots: $$a_n = c_1 r_1^n + c_2 r_2^n$$
Finally, in case of one real root: $$a_n = c_1 r^n + c_2 n r^n$$
Here, from one side I have two complex roots, from the other there is real root with multiplicity 2.
And that's why I don't understand the form of general solution.
Is it possible to generalize the form of solution for recurrence relation of second order on other orders?
Best Answer
You have a root of $2$ with multiplicity $2$, one root of $-i$, and one root of $i$. Therefore:
$$a_n = c_1 2^n + c_2 n 2^n + c_3 (-i)^n + c_4 i^n$$