DHARM62 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEAfter solving we obtain multiple roots – 3, – 3, – 3 and – 3. Therefore, the homogenous
solution is
an = (C 1 n4–1 + C 2 n4–2 + C 3 n4–3 + C 4 n4–4) (– 3)^4 ;
or, an = (C 1 n^3 + C 2 n^2 + C 3 n + C 4 ) (– 3)^4 ;
Example 3.3. Consider the recurrence
an – 11 an–1 + 44 an–2 – 76 an–3 + 48 an–4 = 0
Thus, corresponding characteristic equation is
α^4 – 11 α^3 + 44 α^2 – 76 α + 48 = 0 (here k = 4 and so substitute α^4 for an)
Hence we obtain the roots 2, 2, 3 and 4. Therefore, the homogenous solution is
an = (C 1 n + C 2 ) (2)^2 + C 3 (3)n + C 4 (4)n.3.3.2 Method of Finding Particular Solution...............................................................
The particular solution of the linear difference equation with constant coefficients (or LRRCC)
shown in equation (3.4) is determined by method of inspection. In other words, there is no
general method known for finding out the particular solution of the linear difference equation
with constant coefficients. By inspection, we shall go through following steps,
Step 1
Let the linear difference equation with constant coefficients equation (3.4) is
A 0 an + A 1 an–1 + A 2 an–2 + ...... + Ak an–k = f (n)
Assume that general form of particular solution is decided according to f(n)
Case 1. If f(n) is a polynomial of degree t of n, i.e.,
f(n) = F 1 nt + F 2 nt–1 + ...... + Ft n + Ft+1
(where Fi’s are the coefficients of the polynomial) then, corresponding particular solution will
be of the form
P 1 nt + P 2 nt–1 + ...... + Pt n + Pt+1 (3.15)
where Pi’s are the constants to be determined.
Case 2. If f(n) is a constant, then particular solution is also a constant, let it be P.
Case 3. If f(n) is of form βn where β is not the characteristic root, then corresponding
particular solution is of the form
Pβn (3.16)
Case 3.1. Further, if f(n) is a polynomial of degree t of n followed by βn i.e.
(F 1 nt + F 2 nt–1 + ...... + Ft n + Ft+1) βn
then corresponding particular solution is of the form
(P 1 nt + P 2 nt–1 + ...... + Pt n + Pt+1) βn (3.17)
where Pi’s are the constants to be determined
Case 4. If f(n) is a polynomial of degree t of n followed by βn , where β is a characteristic
root of multiplicity (m – 1) i.e.
(F 1 nt + F 2 nt–1 + ...... + Ft n + Ft+1) βn
then corresponding particular solution is of the form
nm–1(P 1 nt + P 2 nt–1 + ...... + Pt n + Pt+1) βn (3.18)
where Pi’s are the constants to be determined.