Question

Determine the solution for the recurrence relation bn=8bn-1−12bn-2 with b0=3 and b1=4.

(a) 7/2*2^n−1/2*6^n

(b) 2/3*7^n-5*4^n

(c) 4!*6^n

(d) 2/8^n

This question was addressed to me during an internship interview.

My question comes from Advanced Counting Techniques in portion Counting of Discrete Mathematics

Answer 1

The correct answer is (a) 7/2*2^n−1/2*6^n

The best explanation: Rewrite the recurrence relation bn-8bn-1+12bn-2=0. Now from the characteristic equation: x^2−8x+12=0 we have x: (x−2)(x−6)=0, so x=2 and x=6 are the characteristic roots. Therefore the solution to the recurrence relation will have the form: bn=b2^n+c6^n. To find b and c, set n=0 and n=1 to get a system of two equations with two unknowns: 3=b2^0+c6^0=b+c, and 4=b2^1+c6^1=2b+6c. Solving this system gives c=-1/2 and b=7/2. So the solution to the recurrence relation is, bn=7/2*2^n−1/2*6^n.