I have the following non-homogenous recurrence relation and I'm trying to solve it using characteristics roots method :
$a_n = 10a_{n-1} -37a_{n-2} + 60a_{n-3} -36a_{n-4} +4$ for $n \ge4$ and $ a_3 = a_2 = a_1 = a_0 = 1$
I found the particular solution p =1 and I'm trying to solve the homogenous equation when $a_n = r^n$ but it will be an equation of the fourth order !!My question is whether this is the right path or there's any shortcut to solve this problem?
On
Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtractions in indices: $$ a_{n + 4} = 10 a_{n + 3} - 37 a_{n + 2} + 60 a_{n + 1} - 36 a_n + 4 $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize sums like: $$ \sum_{n \ge 0} a_{n + k} z^n = \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k - 1}}{z^k} $$ to get: $$ \frac{A(z) - 1 - z - z^2 - z^3}{z^4} = 10 \frac{A(z) - 1 - z - z^2}{z^3} - 37 \frac{A(z) - 1 - z}{z^2} + 60 \frac{A(z) - 1}{z} - 36 A(z) + 4 \frac{1}{1 - z} $$ Surprisingly it turns out that: $$ A(z) = \frac{1}{1 - z} $$ so that $$ a_n = 1 $$
maxima did the heavy lifting.
We have $$(a_n+1)-10(a_{n-1}+1)+37(a_{n-2}+1)-60(a_{n-3}+1)+36(a_{n-4}+1)=0$$
Set $a_n+1=b_n$ and use this