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?

  • $\begingroup$ it should be $$a_n=c_1 i^n+c_2 (-i)^n+2^n \left(c_4 n+c_3\right)$$ $\endgroup$ – Dr. Sonnhard Graubner May 19 '17 at 15:17
  • $\begingroup$ @Dr.SonnhardGraubner So, basically I just have to combine several cases, right? $\endgroup$ – False Promise May 19 '17 at 15:22
  • $\begingroup$ 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. $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.