Answer to Question #144861 in Discrete Mathematics for Ankita

Question #144861
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
1
Expert's answer
2020-11-18T18:23:57-0500

a)an=3an1+4an2 n2,a0=a1=1a) a_n = 3a_{n-1} +4a_{n-2}\space n \ge 2, a_0=a_1=1\\

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

Now form the characteristic equation:

x23x4=0x=1 and x=4x^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:

an=a(1)n+b4na_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+b40=a+b1=a(1)1+b41=4baa=35 and b=25 answer:an=35(1)n+254n1 = 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)an=an2 n2,a0=a1=1b) a_n = a_{n-2}\space n \ge 2, a_0=a_1=1\\

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

Now form the characteristic equation:

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

We therefore know that the solution to the recurrence

relation will have the form:

an=a(1)n+b1na_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+b10=a+b1=a(1)1+b11=baa=0 and b=1 answer:an=11n=11 = 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)an=2an1an2 n2,a0=a1=2c) a_n = 2a_{n-1} -a_{n-2} \space n \ge 2, a_0=a_1=2\\

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

Now form the characteristic equation:

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

We therefore know that the solution to the recurrence

relation will have the form:

an=a(1)n+bn1n=a+bna_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+b0=a2=a+b1=a+ba=2 and b=0 answer:an=2+0n=22 = 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)an=3an13an2 n3,a0=a1=1,a2=2d) a_n = 3a_{n-1} -3a_{n-2} \space n \ge 3, a_0=a_1=1, a_2 = 2\\

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

Now form the characteristic equation:

x23x+3=0x=1/2(3i3) orx=1/2(3+i3)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:

an=a(1/2(3i3))n+b(1/2(3+i3))na_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+b1=a(1/2(3i3))+b(1/2(3+i3))1/2(3+i3)1=ai3a=1/6(3+i3)b=1/6(9i3) answer:an=1/6(3+i3)(1/2(3i3))n+1/6(9i3)(1/2(3+i3))n1 = 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



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment