Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 63

Step 2

Substitute general form of the particular solution into difference equation (3.4) to ob-

tain the constant/s Pi’s.

Step 3

Put values of constant/s Pi’s into the general form of particular solution we get the
required particular solution.
Example 3.4. Determine the particular solution for the following difference equations :
(a) an + 5 an–1 + 6 an–2 = 3 n^2 – 2n +1 ; (b) an + 5 an–1 + 6 an–2 = 1 ;
(c) an + 5 an–1 + 6 an–2 = 3. 2n ; (d) an + an–1 = 2 n .3n ;
(e) an – 2 an–1 = 3. 2n ; (f) an – 2 an–1 + an–2 = (n + 1). 2n ;
(g) an = an–1 + 5 ; (h) an – 2 an–1 + an–2 = 7;
(i) an – 5 an–1 + 6 an–2 = 3n + n.
Sol.
(a) Comparing the given recurrence an + 5 an–1 + 6 an–2 = 3 n^2 – 2n + 1 with the difference
equation (3.4) we find f(n) = 3 n^2 – 2n + 1 ; which is a polynomial of degree 2, thus we assume
the particular solution will be of the form
P 1 n^2 + P 2 n + P 3 [From equation (3.15]
Substitute above expression into given recurrence/difference equation, we obtain
(P 1 n^2 + P 2 n + P 3 ) – 5 (P 1 (n – 1)^2 + P 2 (n – 1) + P 3 ) + 6 (P 1 (n – 2)^2

• P 2 (n – 2) + P 3 ) = 3n^2 – 2n + 1;
  which is simplifies to
  12P 1 n^2 – (34P 1 – 12P 2 )n + (29P 1 – 17P 2 + 12P 3 ) = 3n^2 – 2n +1 ; (3.19)
  Coefficients P 1 , P 2 and P 3 are determine by comparing the coefficients of n^2 , n and n 0 in
  the equation (3.19). Thus, we obtain the equations,
  12 P 1 = 3;
  34 P 1 – 12 P 2 = 2;
  29 P 1 – 17 P 2 + 12 P 3 = 1;
  which yields P 1 = 1/4, P 2 = 13/24, and P 3 = 71/288;
  Therefore, the particular solution is
  an(p) = 1/4 n^2 + 13/24 n + 71/288;
  (b) For the difference equation an + 5 an–1 + 6 an–2 = 1; we find f(n) = 1, which is a
  constant. So particular solution will also a constant P. Substituting P into the difference equa-
  tion we obtain,
  P + 5 P + 6 P = 1 ;
  so P = 1/12 ;
  Hence, particular solution is
  an(p) = 1/12;
  (c) Consider difference equation
  an + 5 an–1 + 6 an–2 = 3. 2n
  Here, f(n) = 3.2n, that is of form βn (where β = 2 and not a characteristic root). So, we
  assume the general form of the particular solution is like expression (3.16), i.e.
  P βn or P 2n