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?
Best Answer
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.