190
Recursion, Recurrence Relations, and Analysis of Algorithms
for all n ≥ 1. The “for all n ≥ 1” phrase suggests a proof by mathematical induction. Because S(n) has to “reach back” two values to compute the current value,
we should use the second principle of induction.
Base Cases:
When n = 1, the proposed solution gives
S(1) = pr
1−1
1
+ qr
1−1
2
= p + q
When n = 2, the proposed solution gives
S(2) = pr
2−1
1
+ qr
2−1
2
= pr 1 + qr 2
Both are trivially true because we chose p and q to meet these very conditions.
Assume that for all r, 1 ≤ r ≤ k, S(r) = pr
r−1
1
+ qr
r−1
2 . Show that
S(k + 1) = pr
k
1 + qr
k
2 . Before we proceed, note that because r 1 and r 2 are solutions
of the equation t
2
− c 1 t − c 2 = 0, it is true that
r
2
1 − c 1 r 1 − c 2 = 0
or
r
2
1 = c 1 r 1 + c 2
r
2
2 − c 1 r 2 − c 2 = 0
or
r
2
2 = c 1 r 2 + c 2
(15)
Now
S(k + 1) = c 1 S(k) + c 2 S(k − 1)
(by the recurrence relation)
= c 1 (pr
k−1
1
+ qr
k−1
2
) + c 2 (pr
k−2
1
+ qr
k−2
2
)
(by the inductive
= pr
k−2
1
(c 2 + c 1 r 1 ) + qr
k−2
2
(c 2 + c 1 r 2 )
hypothesis, applied twice)
= pr
k−2
1
r
2
1 + qr
k−2
2
r
2
2
(by Equation (15))
= pr
k
1 + qr
k
2
which is the desired result. This confirms that Equation (12) is a solution to
Equation (8).
The key to the solution is the quadratic equation
t 
2
− c 1 t − c 2 = 0
which is called the characteristic equation of the recurrence relation
S(n) = c 1 S(n − 1) + c 2 S(n − 2)
example 21
Solve the recurrence relation
S(n) = 2S(n − 1) + 3S(n − 2) for n ≥ 3
subject to the initial conditions
S(1) = 3
S(2) = 1