Solve the recurrence
$a_n – 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$
with initial conditions $a_1 = 1, a_2 =5$ and $a_3 = 17$ How this was calculated? any hint or idea highly appreciated
Solve the recurrence relation $a_n – 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$
combinatorics
Related Solutions
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.
Starting from $$\frac{z^2}{1-5z+8z^2-4z^3}$$ then \begin{align} \sum_{n=0}^{\infty} a_{n} \, x^n &= \frac{x^2}{1-5x+8x^2-4x^3} = \frac{x^2}{(1-x)(1-2 x)^2} \\ &= \frac{1}{1 - x} - \frac{3}{2 (1 - 2 x)} + \frac{1}{2 \, (1 - 2 x)^2} \\ &= \sum_{n} x^n - \frac{3}{2} \, \sum_{n} 2^n \, x^n + \frac{1}{2} \, \sum_{n} 2^n (n+1) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 - 3 \cdot 2^{n-1} + 2^{n-1} \, (n+1) \right) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 + 2^{n-1} \, (n-2) \right) \, x^n \end{align} which gives $$ a_{n} = 1 + 2^{n-1} \, (n-2). $$
As a check: \begin{align} \phi_{n} &= 5 \, a_{n-1} - 8 \, a_{n-2} + 4 \, a_{n-3} \\ &= (5 - 8 + 4) + 2^{n-4} \, (5 \cdot 4 \, (n-3) - 8 \cdot 2 \, (n-4) + 4 \, (n-5)) \\ &= 1 + 2^{n-1} \, (n-2) = a_{n} \end{align} which is the expected result.
Best Answer
Hint: I'd suggest using characteristic polynomials. This particular recurrence can be made homogeneous linear from: $$a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$$ $$a_{n-1} - 5a_{n-2} +8a_{n-3} -4a_{n-4} = 3^{n-1}$$ and $$a_n - 5a_{n-1} +8a_{n-2} -4a_{n-3} = 3^n$$ $$3a_{n-1} - 15a_{n-2} +24a_{n-3} -12a_{n-4} = 3^n$$ and subtracting $$a_n-8a_{n-1}+23a_{n-2}-28a_{n-3}+12a_{n-4}=0$$ which leads to the following characteristic polynomial: $$x^4-8x^3+23x^2-28x+12=0$$ Integers solutions (if any, rational roots theorem) should be divisors of $12$ and indeed $1,2,3$ are the solutions. Or $$x^4-8x^3+23x^2-28x+12=(x-1)(x-2)^2(x-3)$$ Everything else is mechanics, here and here are a few examples to help you finish the exercise.