2
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .