Kenneth Rosen Edition 7 Exercise 8.2 Question 18 (Page No. 525)

Question

Solve the recurrence relation $a_{n} = 6a_{n−1} − 12a_{n−2} + 8a_{n−3} \:\text{with}\: a_{0} = −5, a_{1} = 4,\: \text{and}\: a_{2} = 88.$

Answer 1

The characteristic polynomial equals

$ x^{3}−6x^{2}+12x−8$

=$ (x−2)^{3}$ .

$an = γ12^{ n} + γ2n2^{ n} + γ3n^{2}2^{ n}$ for some constants$ γ1, γ2, γ3. $

By substituting n = 0, 1, 2 into this equation, we obtain the linear system

$γ1 = −5$ ,

$2γ1 + 2γ2 + 2γ3 = 4$

$4γ1 + 8γ2 + 16γ3 = 88.$

The solution is these equations $γ1 = −5 , c2 = 1/2, c3 = 13/2,$

and therefore $an = −5 · 2^{ n} + n · 2^{ n−1} + 13 · n^{ 2} · 2^{ n−1}$ for n = 0, 1, 2, 3, . . . .