Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Solving Recurrence Relations-Repeated Substitution

In this section we present a technique for solving a recurrence relation such as Equation gif called repeated substitution . The basic idea is this: Given that tex2html_wrap_inline58309, then we may also write tex2html_wrap_inline58311, provided n>1. Since T(n-1) appears in the right-hand side of the former equation, we can substitute for it the entire right-hand side of the latter. By repeating this process we get

eqnarray469

The next step takes a little intuition: We must try to discern the pattern which is emerging. In this case it is obvious:

displaymath58307

where tex2html_wrap_inline58317. Of course, if we have doubts about our intuition, we can always check our result by induction:

Base Case Clearly the formula is correct for k=1, since tex2html_wrap_inline58321.

Inductive Hypothesis Assume that tex2html_wrap_inline58323 for tex2html_wrap_inline58325. By this assumption

  equation473

Note also that using the original recurrence relation we can write

  equation476

for tex2html_wrap_inline58327. Substituting Equation gif in the right-hand side of Equation gif gives

eqnarray481

Therefore, by induction on l, our formula is correct for all tex2html_wrap_inline58331.

So, we have shown that tex2html_wrap_inline58323, for tex2html_wrap_inline58317. Now, if n was known, we would repeat the process of substitution until we got T(0) on the right hand side. The fact that n is unknown should not deter us--we get T(0) on the right hand side when n-k=0. I.e., k=n. Letting k=n we get

  eqnarray483

where tex2html_wrap_inline58303 and tex2html_wrap_inline58305.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.