Answer to Question #302425 in Discrete Mathematics for Snave

Question

Solve the recurrence relation A(n) = 6A(n - 1) - 11A(n - 2) + 6A(n - 3) subject to initial values A(1) = 2, A(2) = 6, A(3) = 20.

Answer 1

The characteristic equation of the recurrence relation is

$r^3 - 6r^2+ 11r-6 = 0$

$(r-1)(r-2)(r-3)=0$

Hence

$a_n=b_1+b_22^n+b_33^n$

$a_1=2, 2=b_1+2b_2+3b_3$

$a_2=6, 6=b_1+4b_2+9b_3$

$a_3=20, 20=b_1+8b_2+27b_3$

$b_1+2b_2+3b_3=2$

$2b_2+6b_3=4$

$6b_2+24b_3=18$

$b_1+2b_2+3b_3=2$

$b_2=2-3b_3$

$2-3b_3+4b_3=3$

$b_1=1$

$b_2=-1$

$b_3=1$

The required solution is

$a_n=1-2^n+3^n$