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?
 A: 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$$
A: 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.
