recurrence-relations
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?
Hint
The treatment with the repeated roots is as follows:
if a root $r$ was repeated of order, say $k$ , then the corresponding terms in the general recurrence will become$$t_n=P_k(n)\cdot r^n$$where $P_k(n)$ is a polynomial of degree $k-1$.
In our case, it will be:$$a_n=(a+bn)\cdot 4^n+c\cdot 2^n$$
I made a spreadsheet, calculating $a_n$ further than you did, and saw a pattern,
where $a_n$ became close to powers of $2$.
I then made an additional column with the difference between $a_n$ and $2^{n+1}$
and saw a further obvious pattern there.
That led me to hypothesize that $a_n=2^{n+1}-n$, which I then easily proved by induction.
Best Answer
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