Answer to Question #301576 in Discrete Mathematics for yoha

Question

Solve the following set of recurrence relations and initial conditions an = 4an−1 + n 2 − n , n ≥ 1; a0 = 1?

Answer 1

Let us solve the following recurrence relation and initial condition

$a_n = 4a_{n−1} + n^2 − n ,\ n ≥ 1;\ a_0 = 1$

The characteristic equation $k-4=0$ has the root $k=4,$ and hence the general solution of the reccurence relation is of the form

$a_n=A\cdot4^n+b_n,$ where the particular solution $b_n=pn^2+qn+r.$

It follows that

$pn^2+qn+r=4(p(n-1)^2+q(n-1)+r)+n^2-n\\=4pn^2-8pn+4p+4qn-4q+4r+n^2-n.$

Therefore,

$(3p+1)n^2+(-8p+3q-1)n+(4p-4q+3r)=0.$

We conclude that

$3p+1=0,\ -8p+3q-1=0,\ 4p-4q+3r=0.$

Then

$p=-\frac{1}3,\\ q=\frac{1}3(1+8p)=\frac{1}3(1-\frac{8}3)=-\frac{5}{9}, \\ r=\frac{4}3(q-p)=\frac{4}3(-\frac{5}9+\frac{1}3)=-\frac{8}{27}.$

We conclude that the general solution of relation is the following:

$a_n=A\cdot4^n-\frac{1}3n^2-\frac{5}9n-\frac{8}{27}.$

Since $a_0 = 1,$ we get $1=a_0=A-\frac{8}{27}.$ Then $A=1+\frac{8}{27}=\frac{35}{27}.$

Consequently, the solution of the recurrence relation with initial condition is

$a_n=\frac{35}{27}\cdot4^n-\frac{1}3n^2-\frac{5}9n-\frac{8}{27}.$