Solving First-Order Recurrence Relations
555
In this case, c = 2, f(n) = 1 for all n > 1, and the boundary value is given for k = 1. Since
T(n) is given as a function of T(n - 1), this is a first-order recurrence relation. Because
the function f is not the zero function, it is called nonhomogeneous.
9.2.1 Solving First-Order Recurrences Using Back Substitution
After finding a solution for the general first-order recurrence relation with constant
coefficient for T(n - 1), we will apply the result to solving some special cases.
Theorem 2. (Solution of First-Order Recurrence Relations) The solution of
T(n)= IcT(n-1)÷ f(n) forn>k
If (k)
for n = k
where c is a constant and f is a nonzero function of n for n > k is
n
T(n) =
cn-lf(l)
l=k
Motivation for the Proof. First, use back substitution to decide what the general form
of the solution might be, and then prove by induction that this is the solution:
T(n) = cT(n - 1) + f(n)
= c(cT(n - 2) + f(n - 1)) ± f(n)
= c
2 T(n - 2) + cf(n - 1) + f(n)
= c
2 (cT(n - 3) + f(n - 2)) + cf (n - 1) + f(n)
= c
3 T(n - 3) + c
2 f(n - 2) + cf(n - 1) + f(n)
Using back substitution one more time gives
n
T(n) = c
3 [cT(n - 4) + f(n - 3)] + -cn-lf(l)
l=n-2
n
= c
4 T(n - 4) + c
3 f(n - 3) + Y cn-lf()
l=n-2
n
= c
4 T(n - 4) + -
cn-f(l)
l=n-3
If back substitution is continued until the argument of T is k-that is, for n - k steps-then
the expression for T(n) becomes
n
T (n) = cn-k T(n -- (n -- k)) +4 E
cn-l f(l)
I=n-k+l
n
= cn-kT(k) +
E
cn-lf(1)
l=n-k+l