Find the solution to the recurrence relation $a_n=4a_{n-1}-5a_{n-2}+(-1)^n$, where $a_0 = 1, a_1 = 1, n \geq 2$

Question

Solve the recurrence relation $a_n$$=4a_{n-1}-5a_{n-2}+(-1)^n$, where $a_0 = 1, a_1 = 1, n \geq 2$.

For the characteristic polynomial $r^2 -4r+5=0$ the two roots are $r=2+i$ and $r=2-i$.

So I found the two roots. How do I go from here to solve the non-homogenous part of the relation?

Answer 1

Use generating functions, as taught by Wilf in generatingfunctionology (2nd edition, Academic Press, 1994). Define:

$\begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \end{align*}$

Shift the recurrence so there are no subtractions in indices, multiply by $z^n$, sum over the values of $n$ where the recurrence is valid and recognize the resulting sums; use the initial values and solve for $A(z)$:

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

In the end, we want the coefficient of $z^n$ in this, the path is to use partial fractions and expand as geometric series (or using the binomial theorem). The problem here is that the factors of the second denominator are complex conjugates:

$\begin{align*} \frac{9 - 25 z}{1 - 4 z + 5 z^2} &= \frac{9 - 25 z}{(1 - (2 - i) z) (1 - (2 + i) z)} \\ &= \frac{9 - 7 i}{2 (1 - (2 - i) z)} + \frac{9 + 7 i}{2 (1 - (2 + i) z)} \end{align*}$

Thus it decomposes into two complex conjugate terms:

$\begin{align*} [z^n] \frac{9 - 25 z}{1 - 4 z + 5 z^2} &= \frac{9 - 7 i}{2} \cdot (2 - i)^n + \frac{9 + 7 i}{2} \cdot (2 + i)^n \end{align*}$

The sum is just twice the real part of, say, the first term. Write the first term in polar form:

$\begin{align*} 2 \Re\left( \frac{9 - 7 i}{2} \cdot (2 - i)^n \right) &= 2 \Re\left( \rho_c \mathrm{e}^{i \theta_c} \cdot \rho^n \mathrm{e}^{i n \theta} \right) \\ &= 2 \rho_c \cdot \rho^n \cdot \cos (\theta_c + n \theta) \end{align*}$

This form of the solution is nice in that it shows directly that:

$\begin{align*} a_n &= \frac{1}{10} (-1)^n + \Theta\left( 2 \rho_c \cdot \rho^n \right) \\ &= \Theta\left( \sqrt{3}^n \right) \end{align*}$

There certainly is a way of writing this as an algebraic expression, but it will involve assorted surds.

Answer 2

The roots of the characteristic polynomial $r_1,r_2$ give rise to the general solution of the homogeneous part of the recurrence, as $c_1 r_1^n+c_2 r_2^n$. The non-homogeneous part is already in this form, but with $r_3=-1$, and since $r_1\not=r_2\not=r_3$ the general solution of the recurrence can be written as $$ c_1(2+i)^n+c_2(2-i)^n+c_3(-1)^n. $$ You can find $a_2=4-5+1$ directly from the recurrence, then use the known values of $a_0,a_1,a_2$ to solve for $c_1,c_2,c_3$.

Another way to see why this works: you can turn the non-homogeneous second order recurrence relation into a homogeneous third order recurrence relation with characteristic polynomial $(r^2-4r+5)(r+1)$ by adding the recurrences for $a_n$ and $a_{n-1}$ (so that the $(-1)^n$ cancels out, and an $a_{n-3}$ term appears).