Question

If Sn=4Sn-1+12n, where S0=6 and S1=7, find the solution for the recurrence relation.

(a) an=7(2^n)−29/6n6^n

(b) an=6(6^n)+6/7n6^n

(c) an=6(3^n+1)−5n

(d) an=nn−2/6n6^n

This question was addressed to me in quiz.

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

Answer 1

The correct option is (b) an=6(6^n)+6/7n6^n

Explanation: The characteristic equation of the recurrence relation is → x^2−4x-12=0

So, (x-6)(x+2)=0. Only the characteristic root is 6. Therefore the solution to the recurrence relation will have the form: an=a.6^n+b.n.6^n. To find a and b, set n=0 and n=1 to get a system of two equations with two unknowns: 6=a6^0+b.0.6^0=a and 7=a6^1+b.1.6^1=2a+6b. Solving this system gives a=6 and b=6/7. So the solution to the recurrence relation is, an=6(6^n)−6/7n6^n.