# 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)$$ Commented May 19, 2017 at 15:17
• @Dr.SonnhardGraubner So, basically I just have to combine several cases, right? Commented May 19, 2017 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. Commented May 19, 2017 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$$

Generating functions make it transparent. Define $$A(z) = \sum_{n \ge 0} a_n z^n$$, shift your recurrence by 4, sum over $$n \ge 0$$, recognize resulting sums:

\begin{align*} \sum_{n \ge 0} a_{n + 4} z^n &= 4 \sum_{n \ge 0} a_{n + 3} z^n - 5 \sum_{n \ge 0} a_{n + 2} z^n + 4 \sum_{n \ge 0} a_{n + 1} z^n - 4 \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z - a_2 z^2 - a_3 z^3}{z^4} &= 4 \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} - 5 \frac{A(z) - a_0 - a_1 z}{z^2} + 4 \frac{A(z) - a_0}{z} - 4 A(z) \end{align*}

Solve for $$A(z)$$, split into partial fractions:

\begin{align*} A(z) &= \frac{a_0 + (a_1 - 4 a_0) z + (a_2 - 4 a_1 + 5 a_0) z^2 + (a_3 - 2 a_2 + 5 a_1 - 4 a_0) z^3} {1 - 4 z + 5 z^2 - 4 z^3 + 4 z^4} \\ &= \frac{a_0 + (a_1 - 4 a_0) z + (a_2 - 4 a_1 + 5 a_0) z^2 + (a_3 - 2 a_2 + 5 a_1 - 4 a_0) z^3} {(1 - 2 z)^2 (1 + z^2)} \\ &= \frac{C}{1 - i z} + \frac{D}{1 + i z} + \frac{E}{1 - 2 z} + \frac{F}{(1 - 2 z)^2} \end{align*}

This for some complicated expressions $$C, D, E, F$$ in the initial values $$a_0, \dotsc, a_3$$, where $$C$$ and $$D$$ are complex. You want the coefficient of $$z^n$$ of this mess. But:

\begin{align*} \frac{1}{1 - a z}1 &= \sum_{n \ge 0} z^n \\ \frac{1}{(1 - a z)^m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} a^n z^n \\ &= \sum_{n \ge 0} \binom{n + m - 1}{m - 1} a^n z^n \end{align*}

and you see the resulting coefficient is:

\begin{align*} [z^n] A(z) &= C \cdot i^n + D \cdot (-i)^n + E \cdot 2^n + F \cdot \binom{n + 1}{1} \cdot 2^n \\ &= C \cdot i^n + D \cdot (-i)^n + (F n + (E + F)) \cdot 2^n \end{align*}

An alternative way to handle a term $$\frac{A + B z}{1 + z^2}$$ is to tackle it directly:

\begin{align*} [z^n] \frac{A + B z}{1 + z^2} &= A [z^n] \frac{1}{1 + z^2} + B [z^{n - 1}] \frac{1}{1 + z^2} \end{align*}

This is $$(-1)^k A$$ if $$n = 2 k$$ is even, $$(-1)^k B$$ if $$n = 2 k + 1$$ is odd.