Section 3.2 Recurrence Relations
183
In Example 14, Section 2.2, we proved by induction that the value of this summation is n
2
.
In summation notation, Equation (7) becomes
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i)
Induction can be used, much as was done in Example 15, to verify that this formula is the solution to recurrence relation (6) (see Exercise 26).
Therefore, the solution to the recurrence relation (6) is
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i)
(8)
This is not yet a closed-form solution, however, because we must find an expression for the summation. Usually it is either trivial to find the sum or we found its
value in Section 2.2 using mathematical induction. (If we can’t find an expression
for the summation, we are really no better off than before. We must iterate through
the summation to find the desired value as opposed to iterating through the recurrence relation to get the desired value.)
The work we’ve done here gives a general solution—Equation (8)—once and
for all for any recurrence relation of the form shown in (6); this work need not be
repeated. All that is necessary is to match your problem to equation (6) to find the
value for c and the formula for g(n) and then plug these results into the expression
in (8). The g(n) in Equation (6) is the usual notation for a function of n; although
we will study functions formally in Chapter 5, you can think of g(n) as giving a
“recipe” for what to do with its argument n. If, for example,
g(n) = 2n
then g doubles whatever its argument value is:
g(3) = 2(3) = 6
g(27) = 2(27) = 54
and
g(i) = 2i
This last value, 2i, would be used in Equation (8) if g(n) = 2n.
You now have a choice of two alternative ways to solve a linear, first-order recurrence relation with constant coefficients. Table 3.2 summarizes these approaches.
example 16
The sequence S(n) of Example 15,
S(1) = 2
S(n) = 2S(n − 1) for n ≥ 2
is a linear, first-order, homogeneous recurrence relation with constant coefficients.
In other words, it matches equation (6) with c = 2 and g(n) = 0. Because g(n) = 0,
the g function evaluates to 0 no matter what the argument is. From formula (8), the
closed-form solution is
S(n) = 2
n−1
(2) + ∙
n
i=2
0 = 2
n
which agrees with our previous result.
183
In Example 14, Section 2.2, we proved by induction that the value of this summation is n
2
.
In summation notation, Equation (7) becomes
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i)
Induction can be used, much as was done in Example 15, to verify that this formula is the solution to recurrence relation (6) (see Exercise 26).
Therefore, the solution to the recurrence relation (6) is
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i)
(8)
This is not yet a closed-form solution, however, because we must find an expression for the summation. Usually it is either trivial to find the sum or we found its
value in Section 2.2 using mathematical induction. (If we can’t find an expression
for the summation, we are really no better off than before. We must iterate through
the summation to find the desired value as opposed to iterating through the recurrence relation to get the desired value.)
The work we’ve done here gives a general solution—Equation (8)—once and
for all for any recurrence relation of the form shown in (6); this work need not be
repeated. All that is necessary is to match your problem to equation (6) to find the
value for c and the formula for g(n) and then plug these results into the expression
in (8). The g(n) in Equation (6) is the usual notation for a function of n; although
we will study functions formally in Chapter 5, you can think of g(n) as giving a
“recipe” for what to do with its argument n. If, for example,
g(n) = 2n
then g doubles whatever its argument value is:
g(3) = 2(3) = 6
g(27) = 2(27) = 54
and
g(i) = 2i
This last value, 2i, would be used in Equation (8) if g(n) = 2n.
You now have a choice of two alternative ways to solve a linear, first-order recurrence relation with constant coefficients. Table 3.2 summarizes these approaches.
example 16
The sequence S(n) of Example 15,
S(1) = 2
S(n) = 2S(n − 1) for n ≥ 2
is a linear, first-order, homogeneous recurrence relation with constant coefficients.
In other words, it matches equation (6) with c = 2 and g(n) = 0. Because g(n) = 0,
the g function evaluates to 0 no matter what the argument is. From formula (8), the
closed-form solution is
S(n) = 2
n−1
(2) + ∙
n
i=2
0 = 2
n
which agrees with our previous result.