SecondOrder 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 secondorder linear homogeneous recurrence relation with
constant coefficients is a recurrence relation of the form a_{k}
= A× a_{k
}_{ 1}
+ B× a_{k
}_{ 2}
for all integers k ³
some fixed integer, where A and B are fixed real numbers with B ¹ 0.
"Secondorder" refers to the fact that the expression of a_{k} contains the two previous terms a_{k }_{ 1} and a_{k } _{ 2 }with B ¹ 0, "linear" to the fact that a_{k}_{1} and a_{k}_{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 a_{k}^{0} 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 secondorder linear
homogeneous recurrence relation with constant coefficients:
Lemma
5.8.1
Let A and B be real numbers. A recurrence relation of the form
a_{k} = A× a_{k }_{ 1} + B× a_{k }_{ 2}
is satisfied by the sequence 1, t, t^{2}, t^{3}, ..., t^{n}, ... where t is a nonzero real number, if, and only if, t satisfies the equation
t^{2}  At  B = 0.
The equation t^{2}  At  B = 0 is called the characteristic equation of the recurrence relation.
Example
Consider the recurrence relation: a_{k}
= 3× a_{k
}_{ 1} + 2× a_{k }_{
2} for all integers k ³
2. Find all sequences that satisfy this recurrence relation
and have the form 1, t, t^{2},
t^{3}, ..., t^{n},
... where t is
nonzero. Then find an explicit formula for this recurrence relation
given a_{0} = 1, a_{1}
= 8.
Solution: By Lemma 8.3.1 a_{k}
= 3× a_{k }_{
1} + 2×
a_{k }_{ 2}
is satisfied by a sequence 1, t, t^{2},
t^{3}, ..., t^{n},
... iff t satisfies the characteristic equation t^{2}
 At  B =
0. Since A = 3 and B = 2 our characteristic equation is t^{2}
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 r_{n} = 1, r, r^{ 2}, r^{ 3}, ..., r^{ n}, ... and s_{n} = 1, s, s^{ 2}, s^{ 3}, ..., s^{ n}, ... both satisfy the same secondorder 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
a_{n} = C× r^{n} + D× s^{n}, for all integers n ³ 0.
Theorem 5.8.3 Distinct
Roots Theorem
Suppose a sequence satisfies a recurrence relation
a_{k} = A× a_{k }_{ 1} + B× a_{k }_{ 2}
for real numbers A and B, B ¹ 0, and all integers k ³ 2. If the characteristic equation
t^{2}  At  B = 0
has two distinct roots r and s, then the sequence satisfies the explicit formula
a_{n} = C× r^{n} + D× s^{n},
where C and D are numbers whose values are determined by the values of a_{0} and a_{1}.
The last line of the Distinct Roots Theorem means that C and D are the solutions to the system of simultaneous equations
a_{0} = C× r^{0} + D× s^{0} and a_{1} = C× r^{1} + D× s^{1}, which simplify to
a_{0} = C + D and a_{1} = C× r + D× s.
Example (cont'd) Find an explicit formula for the recurrence relation: a_{k} = 3× a_{k }_{ 1} + 2× a_{k }_{ 2} for all integers k ³ 2, given initial values a_{0} = 1, a_{1} = 8. Our characteristic equation t^{2} 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 a_{0} = C + D = 1 and a_{1} = 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:
a_{n} = C× r^{n} + D× s^{n}, for all integers n ³ 0 
a_{k} = 3× a_{k }_{ 1} + 2× a_{k }_{ 2} for all integers k ³ 2 
a_{0} = C× r^{0} + D× s^{0} = C + D = 1 

a_{1} = C× r + D× s = 8 

a_{2} = C× r^{2} + D× s^{2} = 26 
26 = 3× 8 + 2× 1 
a_{3} = C× r^{3} + D× s^{3} = 94 
94 = 3× 26 + 2× 26 
a_{4} = C× r^{4} + D× s^{4} = 334 
334 = 3× 94 + 2× 26 
a_{25} = C× r^{25} + D× s^{25} = 1.28325450305 x 10^{14} 

Example
A Formula for the Fibonacci Sequence
The Fibonacci sequence satisfies the recurrence relation
F_{k} = F_{k}_{  1} + F_{k}_{  2}, for all integers k ³ 2
with initial conditions
F_{0} = F_{1} = 1.
Find an explicit formula for this sequence.
Solution: Certainly the Fibonacci
relation is a secondorder 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 t^{2}
 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 SingleRoot Theorem
Suppose a sequence satisfies a recurrence relation
a_{k} = A× a_{k }_{ 1} + B× a_{k }_{ 2}
for real numbers A and B, B ¹ 0, and all integers k ³ 2. If the characteristic equation
t^{2}  At  B = 0
has a single real root r, then the sequence satisfies the explicit formula
a_{n} = C× r^{n} + D×n× r^{n},
where C and D are numbers whose values are determined by the values of a_{0} and any other known value of the sequence.
Example
Single Root Case
Suppose a sequence satisfies the recurrence relation
b_{k} = 4b_{k}_{  1}  4b_{k}_{  2} for all integers k ³ 2,
with initial conditions
b_{0} = 1 and b_{1} = 3.
Find an explicit formula for the sequence.
Solution: This relation is a
secondorder linear homogeneous recurrence relation with constant
coefficients. We need to determine the roots of its characteristic
equation to see which theorem to apply. t^{2}
4t + 4 = 0 ®
(t 2)^{2} = 0 has the unique
root t = 2. Now b_{n}
= C× 2^{n}
+ D× n× 2^{n},
using our initial values
b_{0}
= C× 2^{0} + D× 0×
2^{0} = 1, so C = 1 and
b_{1} = 1× 2^{1} + D× 1×
2^{1} = 3
D = 1/2.
b_{n} = 2^{n} + n× 2^{n }/ 2 ® b_{n} = (1 + n / 2)× 2^{n} for all integers n ³ 0.
SOLHCC Theorems / API in Java / SOLHCC.py
In a Nutshell: Recurrence Relations of the
form a_{k} = A× a_{k
} _{ 1} + B× a_{k
} _{ 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, t^{2},
t^{3}, ..., t^{n},
... iff t satisfies the characteristic equation t^{2}
 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
a_{n} = C×
r^{n} + D×
s^{n}, where C and D are real
(possibly complex) numbers. Using initial values a_{0}
and a_{1} we have:
C = a_{0}  D and D = (a_{0}r
 a_{1})/(r  s).
Double root (r) has solution
a_{n} = C×
r^{n} + D×n× r^{n},
where C and D are real (possibly complex) numbers. Using initial values
a_{0} and a_{1}
we have:
C = a_{0} and D = a_{1}/r
 a_{0}.
Quadratic Equation: The equation ax^{2}
+ bx + c = 0 has solutions: x =
(b + sqrt(b^{2}_{
} 4ac))/2a.