Question

Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5.

(a) an = 4 * 2^n – 3^n

(b) an = 3 * 7^n – 5*3^n

(c) an = 5 * 7^n

(d) an = 3! * 5^n

This question was addressed to me during an interview for a job.

This interesting question is from Advanced Counting Techniques in portion Counting of Discrete Mathematics

Answer 1

Right choice is (b) an = 3 * 7^n – 5*3^n

For explanation: The characteristic polynomial is x^2−6x+8. By solving the characteristic equation, x^2−6x+8=0 we get x=2 and x=4, these are the characteristic roots. Therefore we know that the solution to the recurrence relation has the form an=a*2^n+b*4^n, for some constants a and b. Now, by using the initial conditions a0 and a1 we have: a=7/2 and b=-1/2. Therefore the solution to the recurrence relation is: an = 4 * 2^n – 1*3^n = 7/2 * 2^n – 1/2*3^n.