[WPI] [cs2223] [cs2223 text] [News] [Notes] [Recurrence] 

cs2223, D97/98 Solving Recurrence Relations

Linear, constant-coefficient recurrence relations.

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.

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:

Step 1, Find the homogeneous solution to the homogeneous equation, the one which results when you set the RHS to zero (if it is already zero, skip the next two steps and go directly to Step 4. Your "answer" will contain one or more "undetermined coefficients" whose values cannot be determined until step 4.

Step 2. Find the particular solution by guessing a form similar to the RHS. This step does not produce any additional undermined coefficients, nor does it eliminate those from Step 1.

Step 3. Combine the homogeneous and particular solutions.

Step 4. Use boundary or initial conditions to eliminate the undermined constants from Step 1.

Final Thoughts

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 the change of variables methods as descried inSection 4.7.4 of the text, 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 many of the recurrence relations which occur in the analysis of algorithms.

[cs2223 text] [News] [Notes] [Recurrence]

Contents ©1994-1998, Norman Wittels
Updated 19Mar98