Question

Determine the solution of the recurrence relation  Fn=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^n

The question was posed to me in an interview for internship.

Query is from Advanced Counting Techniques topic in section Counting of Discrete Mathematics

Answer 1

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.