Section 3.2 Recurrence Relations
191
In this recurrence relation, c 1 = 2 and c 2 = 3. To find the closed-form solution, we
form the characteristic equation
t
2
− 2t − 3 = 0
which has roots r 1 = 3, r 2 = −1. Equation (12) gives the solution form:
S(n) = p3
n−1
+ q(−1)
n−1
where from Equation (14) p and q satisfy
p + q = 3
p(3) + q(−1) = 1
Solving this system of equations results in p = 1, q = 2. Therefore the closed-form
solution is
S(n) = 3
n−1
+ 2(−1)
n−1
Practice 13
a. Using the base cases and the recurrence relation, compute the first five terms of the sequence
S(n) of Example 21.
b. Check that the closed-form solution formula in Example 21 produces the correct first five terms. ■
Although it would seem at this point that we have the solution method in
hand for any linear second-order homogeneous recurrence relations with constant
coefficients, such is not the case. Consider the system of Equation (14):
p + q = S(1)
pr 1 + qr 2 = S(2)
We can solve the first equation for p—
p = S(1) − q
Practice 14
Solve the recurrence relation
T(n) = 6T(n − 1) −5T(n − 2) for n ≥ 3
subject to the initial conditions
T(1) = 5
T(2) = 13
■