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

cs2223, D97/98 Solving Recurrence Relations - Step 3

Combine the Homogeneous and Particular Solutions

In contrast to the pages for Step 1 and Step 2, this step is exceedingly simple. Add the homogeneous and particular solutions. Here are some Examples:

Example 3_1

A(n) - 2*A(n-1) = 3; A(n) = B*2^n - 3

Example 3_2, based on Example 2_2

A(n) - 2*A(n) = 2*n^2; A(n) = B*2^n - 2*n^2 - 8*n - 12

Example 3_3, based on Example 2_3

A(n) - 2*A(n-1) = 3 + 2^n; A(n) = (B + n) * 2^n - 3

Example 3_4, based on Example 2_4

A(n) - 2*A(n-1) + A(n-2) = 2; A(n) = B + C*n + n^2

Example 3_5

A(n) + A(n-1) - 6*A(n-2) = 2 * 3^n; A(n) = C*2^n + D*(-3)^n + 3*3^n

Note, in this example, that the last two terms cannot be combined (they do not give the same values!) so there is no potential repeated-root problem.

Example 3_6

A(n) - A(n-1) - A(n-2) = 2*n; A(n) = B*((1+sqrt(5))/2)^n + C*((1-sqrt(5))/2)^n - 6 - 2*n

Example 3_7

A(n) - A(n-1) = 3; A(n) = B + 3*n

Example 3_8

A(n) - A(n-1) = n; A(n) = B + (n^2 + n)/2

Note that this is just the geometric series

Example 3_9

A(n) - 2*A(n-1) = n; A(n) = B*2^n - n - 2

Now we're ready to determine the undetermined coefficients by using boundary conditions or initial conditions, in Step 4.--------------------
[WPI Home Page] [cs2223 home page]  [cs2223 text] [News] [Notes] [Recurrence] [Solving] 

Contents ©1994-1998, Norman Wittels
Updated 19Mar98