## B.3 Solving Recurrences by Substitution Sometimes a recurrence can be solved using a technique called ***substitution***. You can try this method if you cannot obtain a solution using the methods in the last two sections. The following examples illustrate the substitution method. Example B.21****We solve the recurrence  In a sense, substitution is the opposite of induction. That is, we start at *n* and work backward:  We then substitute each equality into the previous one, as follows:  The last equality is the result in [Example A.1](LiB0095.html#1293) in [Appendix A](LiB0093.html#1281). **** The recurrence in [Example B.21](LiB0011.html#105) could be solved using the characteristic equation. The recurrence in the following example cannot. Example B.22****We solve the recurrence  First, work backward from *n*:  Then substitute each equation into the previous one:  for *n* not small. The approximate equality is obtained from [Example A.9](LiB0097.html#1319) in [Appendix A](LiB0093.html#1281). ****