1.

Determine the solution of the recurrence relationFn=20Fn-1 − 25Fn-2 where F0=4 and F1=14.(a) an = 14*5^n-1(b) an = 7/2*2^n−1/2*6^n(c) an = 7/2*2^n−3/4*6^n+1(d) an = 3*2^n−1/2*3^nThe question was posed to me in an interview for internship.Query is from Advanced Counting Techniques topic in section Counting of Discrete Mathematics

Answer»

Right answer is (b) an = 7/2*2^n−1/2*6^n

For EXPLANATION: The characteristic equation of the recurrence relation is → x^2−20x+36=0

So, (x-2)(x-18)=0. Hence, there are two REAL roots x1=2 and x2=18. Therefore the solution to the recurrence relation will have the FORM: an=a2^n+b18^n. To find a and b, SET n=0 and n=1 to get a system of two equations with two UNKNOWNS: 4=a2^0+b18^0=a+b and 3=a2^1+b6^1=2a+6b. Solving this system gives b=-1/2 and a=7/2. So the solution to the recurrence relation is,

an = 7/2*2^n−1/2*6^n.


Discussion

No Comment Found

Related InterviewSolutions