Higher order recurrence relation

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?

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

• Why you added 1 to each an? – Lisa Apr 14 '14 at 5:01
• @Lisa, to balance out $4=1-10+37-60+36$ – lab bhattacharjee Apr 14 '14 at 5:03
• But how will you solve the fourth ordered equation? – Lisa Apr 14 '14 at 5:04
• @Lisa, fortunately, the roots are $$3,3,2,2$$ – lab bhattacharjee Apr 14 '14 at 5:06
• How could you know? – Lisa Apr 14 '14 at 5:06

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.