Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

Identifying the recurrence relation simply by iteration and a good guess is often inadequate for even slightly complex relations. A variety of techniques is available for finding explicit formulas for special classes of recursively defined sequences. The method explained here works for the Fibonacci and other similarly defined sequences.

Definition
A second-order linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form ak = A ak - 1 + B ak - 2 for all integers k some fixed integer, where A and B are fixed real numbers with B 0.

"Second-order" refers to the fact that the expression of ak contains the two previous terms ak - 1 and ak - 2 with B 0, "linear" to the fact that ak-1 and ak-2 appear in separate terms and to the first power, "homogeneous" to the fact that the total degree of each term is the same (no ak0 or more commonly, no constant term), and "constant coefficients" to the fact that A and B are fixed real numbers that do not depend on k.

Example
State whether each of the following is a second-order linear homogeneous recurrence relation with constant coefficients:

  1. ak
  2. = 3 ak - 1 + 2 ak - 2
  3. bk
  4. = bk - 1 + bk - 2 + bk - 3
  5. mk
  6. = 1/2 mk - 1 - 3/7 mk - 2
  7. tk
  8. = 2 tk - 2
  9. ak
  10. = 3 ak - 1 + k ak - 2
  11. ak
  12. = 3 ak - 1 + 2 ak - 2 + 1

Lemma 5.8.1
Let A and B be real numbers. A recurrence relation of the form

ak = A ak - 1 + B ak - 2

is satisfied by the sequence 1, t, t2, t3, ..., tn, ... where t is a nonzero real number, if, and only if, t satisfies the equation

t2 - At - B = 0.

The equation t2 - At - B = 0 is called the characteristic equation of the recurrence relation.

Example
Consider the recurrence relation: ak = 3 ak - 1 + 2 ak - 2 for all integers k 2. Find all sequences that satisfy this recurrence relation and have the form 1, t, t2, t3, ..., tn, ... where t is nonzero. Then find an explicit formula for this recurrence relation given a0 = 1, a1 = 8.
Solution: By Lemma 8.3.1 ak = 3 ak - 1 + 2 ak - 2 is satisfied by a sequence 1, t, t2, t3, ..., tn, ... iff t satisfies the characteristic equation t2 - At - B = 0. Since A = 3 and B = 2 our characteristic equation is t2 -3t - 2 = 0. The solutions to this equation are found by the quadratic equation. We will call the roots to the characteristic equation r and s. So r = 3.56155281281 and s = -.56155281281. The sequences

1, r, r 2, r 3, ..., r n, ... and 1, s, s 2, s 3, ..., s n, ...

are the two solutions of this form. Additional solutions can be found by taking linear combinations of these two solutions. Say rn = 1, r, r 2, r 3, ..., r n, ... and sn = 1, s, s 2, s 3, ..., s n, ... both satisfy the same second-order linear homogeneous recurrence relation with constant coefficients, and C and D are numbers then another sequence satisfying this recurrence relation is defined by the formula

an = C rn + D sn, for all integers n 0.

Theorem 5.8.3 Distinct Roots Theorem
Suppose a sequence satisfies a recurrence relation

ak = A ak - 1 + B ak - 2

for real numbers A and B, B 0, and all integers k 2. If the characteristic equation

t2 - At - B = 0

has two distinct roots r and s, then the sequence satisfies the explicit formula

an = C rn + D sn,

where C and D are numbers whose values are determined by the values of a0 and a1.

The last line of the Distinct Roots Theorem means that C and D are the solutions to the system of simultaneous equations

a0 = C r0 + D s0 and a1 = C r1 + D s1, which simplify to

a0 = C + D and a1 = C r + D s.

Example (cont'd) Find an explicit formula for the recurrence relation: ak = 3 ak - 1 + 2 ak - 2 for all integers k 2, given initial values a0 = 1, a1 = 8. Our characteristic equation t2 -3t - 2 = 0 has distinct roots r = 3.56155281281 and s = -.56155281281 (be sure to store these values in your calculator preferably under the names r and s.) By the distinct roots theorem a0 = C + D = 1 and a1 = C r + D s = 8. Two equations, two unknowns, we solve by substitution:

C = 1 - D,

8 = (1 - D)r + D s,

8 = r - D r + D s,

8 - r = -D r + D s,

8 - r = D(s - r),

(8 - r) / (s - r) = D,

D = -1.07648156274, C = 1 - D = 2.07648156274.

Now store these values for C and D in your calculator. Let's test our results:

an = C rn + D sn, for all integers n 0

ak = 3 ak - 1 + 2 ak - 2 for all integers k 2

a0 = C r0 + D s0 = C + D = 1

 

a1 = C r + D s = 8

 

a2 = C r2 + D s2 = 26

26 = 3 8 + 2 1

a3 = C r3 + D s3 = 94

94 = 3 26 + 2 26

a4 = C r4 + D s4 = 334

334 = 3 94 + 2 26

a25 = C r25 + D s25 = 1.28325450305 x 1014

 

 

Example A Formula for the Fibonacci Sequence
The Fibonacci sequence satisfies the recurrence relation

Fk = Fk - 1 + Fk - 2, for all integers k 2

with initial conditions

F0 = F1 = 1.

Find an explicit formula for this sequence.
Solution: Certainly the Fibonacci relation is a second-order linear homogeneous recurrence relation with constant coefficients. We need to determine if its characteristic equation has two distinct roots to satisfy the conditions of the Distinct Roots Theorem. The characteristic equation is t2 - t - 1 = 0, which has solutions:

By the Distinct Roots Theorem, the Fibonacci sequence satisfies the explicit formula

for all integers n 0.

To find C and D we need only solve the system of equations 1 = C + D and 1 = C r + D s, where r and s are the roots of the characteristic equation. Substitute C = 1 - D into the second equation to get

1 = (1 - D) r + D s
1 = r - Dr + Ds
1 - r = -Dr + Ds
1 - r = D(-r + s)
(1 - r) / (s - r) = D
C = (1 - r) / (s - r) - 1
After simplification these solutions are:
,
so,
.

Theorem 5.8.5 Single-Root Theorem
Suppose a sequence satisfies a recurrence relation

ak = A ak - 1 + B ak - 2

for real numbers A and B, B 0, and all integers k 2. If the characteristic equation

t2 - At - B = 0

has a single real root r, then the sequence satisfies the explicit formula

an = C rn + Dn rn,

where C and D are numbers whose values are determined by the values of a0 and any other known value of the sequence.

Example Single Root Case
Suppose a sequence satisfies the recurrence relation

bk = 4bk - 1 - 4bk - 2 for all integers k 2,

with initial conditions

b0 = 1 and b1 = 3.

Find an explicit formula for the sequence.
Solution: This relation is a second-order linear homogeneous recurrence relation with constant coefficients. We need to determine the roots of its characteristic equation to see which theorem to apply. t2 -4t + 4 = 0 (t -2)2 = 0 has the unique root t = 2. Now bn = C 2n + D n 2n, using our initial values

b0 = C 20 + D 0 20 = 1, so C = 1 and
b1 = 1
21 + D 1 21 = 3
D = 1/2.

bn = 2n + n 2n / 2 bn = (1 + n / 2) 2n for all integers n 0.

SOLHCC Theorems / API in Java / SOLHCC.py

In a Nutshell: Recurrence Relations of the form ak = A ak - 1 + B ak - 2 for all integers k some fixed integer, where A and B are fixed real numbers with B 0, is satisfied by a sequence 1, t, t2, t3, ..., tn, ... iff t satisfies the characteristic equation t2 - At - B = 0. Solutions to the characteristic equation come in one of two forms -distinct roots (r, s) or double root (r, s = r).
Distinct roots (r, s) has solution an = C rn + D sn, where C and D are real (possibly complex) numbers. Using initial values a0 and a1 we have:
C = a0 - D and D = (a0r - a1)/(r - s).
Double root (r) has solution an = C rn + Dn rn, where C and D are real (possibly complex) numbers. Using initial values a0 and a1 we have:
C = a0 and D = a1/r - a0.

Quadratic Equation: The equation ax2 + bx + c = 0 has solutions:  x = (-b + sqrt(b2 - 4ac))/2a.