Question

Solve the following recurrence relation
a) an = 3an-1 + 4an-2 n≥2 a0=a1=1
b) an= an-2 n≥2 a0=a1=1
c) an= 2an-1 - an-2. n≥2 a0=a1=2
d) an=3an-1 - 3an-2 n≥3 a0=a1=1 , a2=2

Answer 1

$a) a_n = 3a_{n-1} +4a_{n-2}\space n \ge 2, a_0=a_1=1\\$

Rewrite the recurrence relation $a_n - 3a_{n-1} -4a_{n-2} = 0$.

Now form the characteristic equation:

$x^2 -3x-4 =0\\ x = -1\space and\space x = 4$

We therefore know that the solution to the recurrence

relation will have the form:

$a_n = a *(-1)^n +b*4^n$

To find a and b , plug in n = 0 and n = 1 to get a system of two equations with two unknowns:

$1 = a*(-1)^0+b*4^0 = a+b\\ 1 = a*(-1)^1+b*4^1 =4b - a\\ a = \dfrac{3}{5} \space and \space b = \dfrac{2}{5}\\ \space\\ answer: a_n = \dfrac{3}{5}(-1)^n + \dfrac{2}{5}4^n$

$b) a_n = a_{n-2}\space n \ge 2, a_0=a_1=1\\$

Rewrite the recurrence relation $a_n -a_{n-2} = 0$.

Now form the characteristic equation:

$x^2 -1=0\\ x = -1\space and\space x = 1$

We therefore know that the solution to the recurrence

relation will have the form:

$a_n = a *(-1)^n +b*1^n$

To find a and b , plug in n = 0 and n = 1 to get a system of two equations with two unknowns:

$1 = a*(-1)^0+b*1^0 = a+b\\ 1 = a*(-1)^1+b*1^1 =b - a\\ a = 0 \space and \space b = 1\\ \space\\ answer: a_n = 1*1^n = 1$

$c) a_n = 2a_{n-1} -a_{n-2} \space n \ge 2, a_0=a_1=2\\$

Rewrite the recurrence relation $a_n - 2a_{n-1} +a_{n-2} = 0$.

Now form the characteristic equation:

$x^2 -2x+1 =0\\ x = 1$

We therefore know that the solution to the recurrence

relation will have the form:

$a_n = a *(1)^n +b*n*1^n = a+bn$

To find a and b , plug in n = 0 and n = 1 to get a system of two equations with two unknowns:

$2 = a+b*0 = a\\ 2 = a+b*1 =a +b\\ a = 2 \space and \space b = 0\\ \space\\ answer: a_n = 2 +0*n = 2$

$d) a_n = 3a_{n-1} -3a_{n-2} \space n \ge 3, a_0=a_1=1, a_2 = 2\\$

Rewrite the recurrence relation $a_n - 3a_{n-1} +3a_{n-2} = 0$.

Now form the characteristic equation:

$x^2 -3x+3 =0\\ x = 1/2(3-i\sqrt3)\ or\\ x = 1/2(3+i\sqrt3)$

We therefore know that the solution to the recurrence

relation will have the form:

$a_n = a *(1/2(3-i\sqrt3))^n +b*(1/2(3+i\sqrt3))^n$

To find a and b , plug in n = 0 and n = 1 to get a system of two equations with two unknowns:

$1 = a+b \\ 1 = a*(1/2(3-i\sqrt3))+b*(1/2(3+i\sqrt3))\\ 1/2(3+i\sqrt3)-1 = -ai\sqrt3\\ a= 1/6(-3+i\sqrt3)\\ b= 1/6(9-i\sqrt3)\\ \space\\ answer: \\ a_n = 1/6(-3+i\sqrt3) *(1/2(3-i\sqrt3))^n +1/6(9-i\sqrt3)*(1/2(3+i\sqrt3))^n$