Section 3.2 Recurrence Relations
189
In such a sequence, we must have two “base case” values, that is, two known
values of the sequence in order to generate subsequent values.
We’d like to find a general solution formula for recurrence relations like (9).
If we drop the second term, we of course have a linear first-order homogeneous
recurrence relation with constant coefficients:
S(n) = c 1 S(n − 1)
From Equation (8), we know that the solution to this recurrence relation has the form
S(n) = c
n−1
1
S(1)
Let’s express this solution as
S(n) = pr
n−1
(10)
where r (that is, c 1 ) is the solution (root) of the linear equation
t − c 1 = 0
(11)
and p (that is, S(1)) satisfies equation (10) for the initial condition n = 1:
S(1) = pr
1−1
= pr
0
= p
This viewpoint suggests a way in which we might conjecture a solution to
equation (9). Since we now have two terms in the equation itself, let’s add a second
term to (10) and represent a potential solution as
S(n) = pr
n−1
1
+ qr
n−1
2
(12)
where r 1 and r 2 are two distinct roots of (extending (11) to a quadratic equation)
t
2
− c 1 t − c 2 = 0
(13)
The p and q will have to be chosen to satisfy the two initial conditions:
S(1) = pr
1−1
1
+ qr
1−1
2
= p + q
S(2) = pr
2−1
1
+ qr
2−1
2
= pr 1 + qr 2
or, simplifying,
p + q = S(1)
pr 1 + qr 2 = S(2)
(14)
Of course, this is just a wild leap of speculation on our part, so we must now verify
that Equation (12) is a closed-form solution to recurrence relation (9).
We are trying to prove that
S(n) = pr
n−1
1
+ qr
n−1
2
(where r 1 , r 2 , p, and q are as described) is a solution to
S(n) = c 1 S(n − 1) + c 2 S(n − 2)