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$$