Actually, this page is about how to solve all homogeneous recurrence relations of the above form plus some non-homogeneous - the ones with a few, specific, forcing functions. This note explains, in more detail, how to solve an important subset of the equations described in the lecture note on recurrences, L2, on the Notes page.
The types of equations we can solve using this technique look like this:
All terms containing the sequence we are trying to solve, A, are put on the left-hand side and the right-hand side, RHS., has one of the following forms:
Form | Examples |
Homogeneous | |
A constant to the n-th power | |
A polynomial in n | |
A product of a constant to the n-th power and a polynomial in n | |
A linear combination of any of the above |
This technique is based on the method of characteristic equations with undetermined constants used to solve the related continuous function in differential calculus. It relies on the principle of uniqueness - any answer which works is the correct answer since there is only one correct anwer. That last statement can be proved, but we won't do that here.
There are two parts to the total solution. The homogeneous part of the solution depends only on what is on the left of the recurrence relation. The particular part of the total solution depends on what is in the RHS and has the same form as the RHS. We will calculate the two parts separately and add them to form the total solution.
There are four steps in the process. Each has its own web page with examples:
This method is straightforward and very effective. The major limitation is that it only works with a specific subset of recurrence relations. However, by using substitution of variables methods as descried in the L2 notes, a wider range of recurrence relations can be solved than is immediately apparent. In fact, the method we have presented here is useful for solving most of the recurrence relations which occur in the analysis of algorithms.
[Notes] |