182
Recursion, Recurrence Relations, and Analysis of Algorithms
A Solution Formula
Some types of recurrence relations have known solution formulas. A recurrence
relation for a sequence S(n) is linear if the earlier values of S appearing in the
definition occur only to the first power. The most general linear recurrence relation has the form
S(n) = f 1 (n)S(n − 1) + f 2 (n)S(n − 2) + c + f k (n)S(n − k) + g(n)
where the f i ’s and g can be expressions involving n. The recurrence relation has
constant coefficients if the f i ’s are all constants. It is first-order if the nth term
depends only on term n − 1. Linear first-order recurrence relations with constant
coefficients therefore have the form
S(n) = cS(n − 1) + g(n)
(6)
Finally, a recurrence relation is homogeneous if g(n) = 0 for all n.
We will find the solution formula for equation (6), the general linear firstorder recurrence relation with constant coefficients, subject to the basis that S(1)
is known. We will use the expand, guess, and verify approach. The work here is a
generalization of what was done in Example 15. Repeatedly applying equation (6)
and simplifying, we get
S(n) = cS(n − 1) + g(n)
= c[cS(n − 2) + g(n − 1)] + g(n)
= c
2
S(n − 2) + cg(n − 1) + g(n)
= c
2
[cS(n − 3) + g(n − 2)] + cg(n − 1) + g(n)
= c
3
S(n − 3) + c
2
g(n − 2) + cg(n − 1) + g(n)
f
After k expansions, the general form appears to be
S(n) = c
k
S(n − k) + c
k−1
g(n − (k − 1)) + c + cg(n − 1) + g(n)
If the sequence has a base value at 1, then the expansion terminates when
n − k = 1 or k = n − 1, at which point
S(n) = c
n−1
S(1) + c
n−2
g(2) + c + cg(n − 1) + g(n)
= c
n−1
S(1) + c
n−2
g(2) + c + c
1
g(n − 1) + c
0
g(n)
(7)
We can use summation notation to write part of this expression more compactly.
The uppercase Greek letter sigma, ∙, stands for summation. The notation
∙
q
i=p
(expression)
says to substitute into the expression successive values of i, the index of
summation, from the lower limit p to the upper limit q, and then sum the results.
(See Appendix B for further discussion of summation notation.) Thus, for example,
∙
n
i=1
(2i − 1) = 1 + 3 + 5 + c + (2n − 1)
Recursion, Recurrence Relations, and Analysis of Algorithms
A Solution Formula
Some types of recurrence relations have known solution formulas. A recurrence
relation for a sequence S(n) is linear if the earlier values of S appearing in the
definition occur only to the first power. The most general linear recurrence relation has the form
S(n) = f 1 (n)S(n − 1) + f 2 (n)S(n − 2) + c + f k (n)S(n − k) + g(n)
where the f i ’s and g can be expressions involving n. The recurrence relation has
constant coefficients if the f i ’s are all constants. It is first-order if the nth term
depends only on term n − 1. Linear first-order recurrence relations with constant
coefficients therefore have the form
S(n) = cS(n − 1) + g(n)
(6)
Finally, a recurrence relation is homogeneous if g(n) = 0 for all n.
We will find the solution formula for equation (6), the general linear firstorder recurrence relation with constant coefficients, subject to the basis that S(1)
is known. We will use the expand, guess, and verify approach. The work here is a
generalization of what was done in Example 15. Repeatedly applying equation (6)
and simplifying, we get
S(n) = cS(n − 1) + g(n)
= c[cS(n − 2) + g(n − 1)] + g(n)
= c
2
S(n − 2) + cg(n − 1) + g(n)
= c
2
[cS(n − 3) + g(n − 2)] + cg(n − 1) + g(n)
= c
3
S(n − 3) + c
2
g(n − 2) + cg(n − 1) + g(n)
f
After k expansions, the general form appears to be
S(n) = c
k
S(n − k) + c
k−1
g(n − (k − 1)) + c + cg(n − 1) + g(n)
If the sequence has a base value at 1, then the expansion terminates when
n − k = 1 or k = n − 1, at which point
S(n) = c
n−1
S(1) + c
n−2
g(2) + c + cg(n − 1) + g(n)
= c
n−1
S(1) + c
n−2
g(2) + c + c
1
g(n − 1) + c
0
g(n)
(7)
We can use summation notation to write part of this expression more compactly.
The uppercase Greek letter sigma, ∙, stands for summation. The notation
∙
q
i=p
(expression)
says to substitute into the expression successive values of i, the index of
summation, from the lower limit p to the upper limit q, and then sum the results.
(See Appendix B for further discussion of summation notation.) Thus, for example,
∙
n
i=1
(2i − 1) = 1 + 3 + 5 + c + (2n − 1)