Solving First-Order Recurrence Relations 555In 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>kIf (k) for n = kwhere c is a constant and f is a nonzero function of n for n > k is
nT(n) = cn-lf(l)
l=kMotivation 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
nT(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-3If back substitution is continued until the argument of T is k-that is, for n - k steps-then
the expression for T(n) becomesT (n) = cn-k T(n -- (n -- k)) +4 E n cn-l f(l)
I=n-k+l
n= cn-kT(k) + E cn-lf(1)
l=n-k+l