Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 61

So equation (3.11) is called characteristic equation.
If α 1 is one of the roots of this equation then Aα 1 n is a homogenous solution to the
difference equation.
Step 2
Solve the characteristic equation and find out the roots to satisfy the homogenous equa-
tion. A characteristic equation of kth degree has k characteristic roots. The roots are of
following nature,
Case 1. Let all roots are distinct s.t. α 1 , α 2 , ...... αk then homogenous solution is given as,
an(h) = C 1 α 1 n + C 2 α 2 n + ......+ Ck αkn (3.12)
where Ci’s (1 ≤ i ≤ k) are the constants to be determined (see example 3.1)
Case 2. Suppose some roots of the characteristic equation are multiple roots. Let α 1 be
a root of multiplicity m then homogenous solution is given as,
an(h) = (C 1 nm–1 + C 2 nm–2 + ...... +Cm–1 n + Cm) α 1 n (3.13)
(see example 3.2)
Case 3. If some roots of the characteristic equation are multiple roots and remaining
are distinct (combination of above cases 1 and 2), i.e., α 1 = α 2 = α 3 ; α 4 ≠ α 5 ≠...... ≠ ak then
homogenous solution is
an(h) = (C 1 n^2 + C 2 n + C 3 ) α 13 + C 4 α 4 n + C 5 α 5 n ...... + Ck αkn (3.14)
(see example 3.3)

Step 3

Determine the constants Ci’s (1≤ i ≤ k) using base conditions.

Example 3.1. Consider the Fibonacci number series recurrence equation (3.2), this recurrence
can be equivalently specifies as,
an = an–1 + an–2 (with base conditions are a 0 = 0 and a 1 = 1)
So, the homogenous equation is an – an–1 – an–2 = 0 and its corresponding characteristic
equation is obtain by substituting α^2 for an, i.e.,
α^2 – α – 1 = 0
Hence we obtain two distinct roots (1+^5 )/2 and (1–^5 )/2
Therefore, the homogenous solution
an = C 1 ((1 +^5 )/2)n + C 2 ((1 –^5 )/2)n ;
Coefficient C 1 and C 2 are determined by using base conditions such that put a 0 = 0 and
a 1 = 1 in the homogenous solution.
Thus, we obtain C 1 = 1/5 and C 2 = – 1/5;
Therefore, the homogenous solution is
an = 1/5 ((1+ 5 )/2)n – 1/5 ((1- 5 )/2)n ;

Example 3.2. Consider another recurrence of multiple roots
an – 9an–2 + 4an–3 + 12an–4 = 0.
Thus, we have the characteristic equation is
α^4 – 9α^2 + 4α + 12 = 0 ; (here k = 4 and so substitute α^4 for an)