Recurrence basics
Math 162: Recurrences - more
Ümit Işlak
Boğaziçi Üniversitesi, Matematik Bölümü
May 10, 2022
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Definition
A linear homogeneous recurrence relation of degree k with
constant coefficients is a recurrence relation of the form
an = c1 an−1 + c2 an−2 + · · · + ck an−k
where c1 , . . . , ck ∈ R and ck is non-zero.
Note. Here,
linear means linearity in terms of ai ’s;
homogeneous means that there is no constant term;
constant coefficients means that ci ’s are constants and that
they do not depend on n;
degree k means that an is defined in terms of previous k
members.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Definition
A linear homogeneous recurrence relation of degree k with
constant coefficients is a recurrence relation of the form
an = c1 an−1 + c2 an−2 + · · · + ck an−k
where c1 , . . . , ck ∈ R and ck is non-zero.
Note. Here,
linear means linearity in terms of ai ’s;
homogeneous means that there is no constant term;
constant coefficients means that ci ’s are constants and that
they do not depend on n;
degree k means that an is defined in terms of previous k
members.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Example
(i) an = 2an−1 is a linear homogeneous recurrence relation of
degree 1 with constant coefficient.
(ii) (Lucas numbers) The initial conditions of Lucas numbers are
L0 = 2 and L1 = 1 and the recursive relation is
Ln+2 = Ln+1 + Ln , n ≥ 2.
This is a linear homogeneous recurrence relation of degree 2 with
constant coefficients. This is the same as the Fibonacci recursion
except that the initial conditions are given differently.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Example
(i) an = 2an−1 is a linear homogeneous recurrence relation of
degree 1 with constant coefficient.
(ii) (Lucas numbers) The initial conditions of Lucas numbers are
L0 = 2 and L1 = 1 and the recursive relation is
Ln+2 = Ln+1 + Ln , n ≥ 2.
This is a linear homogeneous recurrence relation of degree 2 with
constant coefficients. This is the same as the Fibonacci recursion
except that the initial conditions are given differently.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Example
(i) an = 2an−1 is a linear homogeneous recurrence relation of
degree 1 with constant coefficient.
(ii) (Lucas numbers) The initial conditions of Lucas numbers are
L0 = 2 and L1 = 1 and the recursive relation is
Ln+2 = Ln+1 + Ln , n ≥ 2.
This is a linear homogeneous recurrence relation of degree 2 with
constant coefficients. This is the same as the Fibonacci recursion
except that the initial conditions are given differently.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Example
The recursion
an = 2na2n−1 + 3
is not linear since we have a2n−1 .
is not homogeneous since we have 3.
does not have constant coefficients since we have n in front of
a2n−1 .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Here we will be looking for solutions of a linear homogeneous
recurrence of the form an = rn where r is some constant. Observe
that an = rn is a solution of
an = c1 an−1 + c2 an−2 + · · · + ck an−k
if and only if
rn = c1 rn−1 + c2 rn−2 + · · · + ck rn−k
if and only if
rk − c1 rk−1 − c2 rk−2 − · · · − ck = 0.
This last equation is called the characteristic equation of the
recurrence. So our conclusion can be restated as: an = rn is a
solution to our recurrence if and only if r is a solution of the
characteristic equation. The roots of the characteristic equation
are called the characteristic roots of the recurrence.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Here we will be looking for solutions of a linear homogeneous
recurrence of the form an = rn where r is some constant. Observe
that an = rn is a solution of
an = c1 an−1 + c2 an−2 + · · · + ck an−k
if and only if
rn = c1 rn−1 + c2 rn−2 + · · · + ck rn−k
if and only if
rk − c1 rk−1 − c2 rk−2 − · · · − ck = 0.
This last equation is called the characteristic equation of the
recurrence. So our conclusion can be restated as: an = rn is a
solution to our recurrence if and only if r is a solution of the
characteristic equation. The roots of the characteristic equation
are called the characteristic roots of the recurrence.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Our goal in this section is to see that the characteristic roots can
be used to give an explicit formula for all the solutions of the
recurrence relation. We discuss the k = 2 case.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Theorem
Let c1 , c2 ∈ R. Suppose
r2 − c1 r − c2 = 0
has two distinct roots r1 and r2 . Then the sequence an is a
solution of the recurrence relation
an = c1 an−1 + c2 an−2
if and only if
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . .
where α1 , α2 are constants.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Example
Find the sequence an that satisfies the recursion
an = an−1 + 2an−2 , n≥2
with the initial conditions a0 = 2 and a1 = 7.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Solution. The characteristic equation in this case is
r2 − r − 2 = 0.
Its roots are r1 = 2 and r2 = −1.Hence an is a solution if and only
if
an = α1 2n + α2 (−1)n
for some constants α1 , α2 . The given initial conditions then imply
a0 = 2 = α1 + α2
and
a1 = 7 = 2α1 − α2 .
Solving these two equations, we obtain α1 = 3, α2 = −1. Hence,
the unique solution to our recurrence relation is given by
an = 3 · 2n − (−1)n .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Solution. The characteristic equation in this case is
r2 − r − 2 = 0.
Its roots are r1 = 2 and r2 = −1.Hence an is a solution if and only
if
an = α1 2n + α2 (−1)n
for some constants α1 , α2 . The given initial conditions then imply
a0 = 2 = α1 + α2
and
a1 = 7 = 2α1 − α2 .
Solving these two equations, we obtain α1 = 3, α2 = −1. Hence,
the unique solution to our recurrence relation is given by
an = 3 · 2n − (−1)n .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Exercise
Consider the Fibonacci sequence defined by setting F0 = 1,
F1 = 1, and the following recursion
Fn+2 = Fn+1 + Fn , n ≥ 0.
Find an explicit formula for Fn .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Proof of the main theorem.
Theorem
Let c1 , c2 ∈ R. Suppose
r2 − c1 r − c2 = 0
has two distinct roots r1 and r2 . Then the sequence an is a
solution of the recurrence relation
an = c1 an−1 + c2 an−2
if and only if
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . .
where α1 , α2 are constants.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Proof. (⇐) We let an = α1 r1n + α2 r2n and show that an solves the
recursion. Since r1 , r2 are solutions to the characteristic equation,
we have
r12 = c1 r1 + c2 , and r22 = c1 r2 + c2 .
Using these
c1 an−1 + c2 an−2 = c1 (α1 r1n−1 + α2 r2n−1 ) + c2 (α1 r1n−2 + α2 r2n−2 )
= α1 r1n−2 (c1 r1 + c2 ) + α2 r2n−2 (c1 r2 + c2 )
= α1 r1n−2 r12 + α2 r2n−2 r22
= α1 r1n + α2 r2n
= an .
So we are done.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
(⇒) This time we claim that every solution an of
an = c1 an−1 + c2 an−2
is of the form
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . .
for some constants α1 , α2 .
Let an be any solution to the recurrence and suppose that the
initial conditions are a0 = C0 and a1 = C1 . We will show that
there are constants α1 , α2 such that the sequence an with
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . ., satisfies the same initial
conditions. This requires
a 0 = C0 = α 1 + α 2 , and a1 = C1 = α1 r1 + α2 r2 .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
(⇒) This time we claim that every solution an of
an = c1 an−1 + c2 an−2
is of the form
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . .
for some constants α1 , α2 .
Let an be any solution to the recurrence and suppose that the
initial conditions are a0 = C0 and a1 = C1 . We will show that
there are constants α1 , α2 such that the sequence an with
an = α1 r1n + α2 r2n , n = 0, 1, 2, . . ., satisfies the same initial
conditions. This requires
a 0 = C0 = α 1 + α 2 , and a1 = C1 = α1 r1 + α2 r2 .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
First of these two says that α2 = C0 − α1 . Inserting this into the
second one gives
C1 = α1 r1 + (C0 − α1 )r2 = α1 (r1 − r2 ) + C0 r2 .
Solving this, we see that
C1 − C0 r2
α1 =
r1 − r2
and
C1 − C0 r2 C0 r1 − C1
α2 = C0 − α1 = C0 − = .
r1 − r2 r1 − r2
(Note that here we used the assumption that r1 6= r2 ). So for
these values of α1 and α2 , α1 r1n + α2 r2n satisfies the two initial
conditions.
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Now we know that an and α1 r1n + α2 r2n are both solutions of the
recurrence relation an = c1 an−1 + c2 an−2 and both satisfy the
initial conditions for n = 0 and n = 1. Since there is a unique
solution of a linear homogeneous recurrence relation of degree two
with two initial conditions, we conclude that the solutions are the
same:
an = α1 r1n + α2 r2n .
Ümit Işlak Math 162: Recurrences - more
Recurrence basics
Arrivederci
Next lecture:
Selamlar, iyi çalışmalar,
Ümit
Ümit Işlak Math 162: Recurrences - more
