Lemma 8.3.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.


Theorem 8.3.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.


Theorem 8.3.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.