Let us find the solution of the recurrence relation an=4an−1−3an−2+2n+n+3 with
a0=1 and a1=4.
The characteristic equation k2−4k+3=0 of the homogeous recurrence relation an−4an−1+3an−2=0 is equivalent to (k−1)(k−3)=0, and hence has the solutions k1=1
and k2=3. Therefore, the general solution of the relation an=4an−1−3an−2+2n+n+3 is of the form an=c1+c23n+bnp, where bnp=a2n+n(bn+c)=a2n+bn2+cn.
It follows that
a2n+bn2+cn
=4(a2n−1+b(n−1)2+c(n−1))−3(a2n−2+b(n−2)2+c(n−2))+2n+n+3
=4a2n−1+4b(n2−2n+1)+4c(n−1)−3a2n−2−3b(n2−4n+4)−3c(n−2)+2n+n+3
=4a2n−1−3a2n−2+2n+bn2+(4b+c+1)n+(−8b+2c+3)
=(5a+4)2n−2+bn2+(4b+c+1)n+(−8b+2c+3).
It follows that 4a=5a+4, c=4b+c+1 and −8b+2c+3=0.
Therefore, a=−4, b=−41, c=21(8b−3)=21(−2−3)=−25.
We conclude that the general solution of the relation an=4an−1−3an−2+2n+n+3 is of the form an=c1+c23n−4⋅2n−41n2−25n.
Since a0=1 and a1=4, we get
1=a0=c1+c2−4 and 4=a1=c1+3c2−8−41−25=c1+3c2−443.
Therefore, c1+c2=5 and c1+3c2=459. It follows that c2=839 and c1=81.
Consequently, the general solution of the relation an=4an−1−3an−2+2n+n+3 is the following:
an=839+813n−2n+2−41n2−25n.