# Find the general solution of recurrence relation of order four

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?

• it should be $$a_n=c_1 i^n+c_2 (-i)^n+2^n \left(c_4 n+c_3\right)$$ – Dr. Sonnhard Graubner May 19 '17 at 15:17
• @Dr.SonnhardGraubner So, basically I just have to combine several cases, right? – False Promise May 19 '17 at 15:22
• Remember that when you solve the characteristic equation, you are searching for solutions of the form $y = cr^n$ where $r$ ends up being your roots. By superposition you can combine all of the solutions you find. If you find double roots, then tack an $n$ on it. This should get you the general solution to any order problem. – Kaynex May 19 '17 at 15:34

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$$