Find a closedform representation of the following recurrence

Find a closed-form representation of the following recurrence relations: a_n = 6a_n - 1 - 9a_n - 2 for n greaterthanorequalto 2 with initial conditions a_0 = 4 and a_1 = 6 a_n = 4a_n - 1 + 5a_n - 2 for n greaterthanorequalto 2 with initial conditions a_0 = 2 and a_1 = 8

Solution

In both parts we have linear homogeneous recurrence relations

In such recurrence relations we assume:a_n=r^n

a)

SUbstituting a_n=r^n gives

r^2=6r-9

r^2-6r+9=0

r=3

So we have repeated roots

So general solution is

a_n=3^n(A+Bn)

Because in case of repeated root say r

r^n and nr^n are both solutions

a_0=A=4

Hence, A=4

a_1=6=3(4+B)

Hence, B=-2

So, a_n=3^n(4-2n)

b)

Substituting gives

r^2=4r+5

r^2-4r-5=0

r^2-5r+r-5=0

r(r-5)+(r-5)=0

r=-1,5

a_n=A(-1)^{n}+B5^n

a_0=A+B=2

a_1=-A+5B=8

So, B=5/3, A=1/3

a_n=(-1)^{n}/3+5*5^n/3