Recurrence relations

discrete math

1. Counting

2. Recurrence Relations
Sequencesare ordered lists of elements.
•1,2,3,5,8
•1,3,9,27,81,…
Sequences arise throughout mathematics, computer
science, and in many other disciplines, ranging from
botany to music.

We will introduce the terminology to represent
sequences.
© S. Turaev, CSC 1700 Discrete Mathematics 2

3. Recurrence Relations
Definition: A sequenceis a function from a subset of the
integers (usually either the set 0,1,2,3,4,…or
1,2,3,4,…) to a set ????????????.
The notation ????????????
????????????is used to denote the image of the
integer ????????????. We can think of ????????????
????????????as the equivalent of
????????????
????????????where ????????????is a function from 0,1,2,…to ????????????. We
call ????????????
????????????a termof the sequence.
Example: Consider the sequence ????????????
????????????where ????????????
????????????=1/????????????.
Then
1,
1
2
,
1
3
,
1
4
,…
© S. Turaev, CSC 1700 Discrete Mathematics 3

4. Recurrence Relations
Definition: A recurrence relation for the sequence ????????????
????????????is
an equation that expresses ????????????
????????????in terms of one or more of
the previous terms of the sequence, namely,
????????????
0,????????????
1,…,????????????
????????????−1, for all integers ???????????? with ????????????≥????????????
0, where ????????????
0
is a nonnegative integer.
A sequence is called a solution of a recurrence relation
if its terms satisfy the recurrence relation.
The initial conditions for a sequence specify the terms
that precede the first term where the recurrence
relation takes effect.
© S. Turaev, CSC 1700 Discrete Mathematics 4

5. Recurrence Relations
Example: Let ????????????
????????????be a sequence that satisfies the
recurrence relation ????????????
????????????=????????????
????????????−1+3for ????????????=1,2,3,4,…
and suppose that ????????????
0=2. What are ????????????
1,????????????
2and ????????????
3?
[Here the initial condition is ????????????
0=2.]
Example: Let ????????????
????????????be a sequence that satisfies the
recurrence relation ????????????
????????????=????????????
????????????−1−????????????
????????????−2for ????????????=2,3,4,…
and suppose that ????????????
0=3and ????????????
1=5. What are ????????????
2and
????????????
3?
[Here the initial conditions are ????????????
0=3and ????????????
1=5.]
© S. Turaev, CSC 1700 Discrete Mathematics 5

6. Fibonacci Numbers
Definition:the Fibonacci sequence, ????????????
0,????????????
1,????????????
2,…,is
defined by:
Initial Conditions: ????????????
0=0,????????????
1=1
Recurrence Relation: ????????????
????????????=????????????
????????????−1+????????????
????????????−2
Example: Find ????????????
4,????????????
5,????????????
6,????????????
7and ????????????
8.
© S. Turaev, CSC 1700 Discrete Mathematics 6

7. Recurrence Relations
Finding a formula for the ????????????th term of the sequence
generated by a recurrence relation is called solving the
recurrence relation.
Such a formula is called a explicit(closed) formula.
One technique for finding an explicit formula for the
sequence defined by a recurrence relation is
backtracking.
© S. Turaev, CSC 1700 Discrete Mathematics 7

8. Recurrence Relations
Example: Let ????????????
????????????be a sequence that satisfies the
recurrence relation ????????????
????????????=????????????
????????????−1+3for ????????????=2,3,4,…and
suppose that ????????????
1=2. Find an explicit formula for the
sequence.
????????????
????????????=????????????
????????????−1+3
=????????????
????????????−2+3+3=????????????
????????????−2+2⋅3
=????????????
????????????−3+3+2⋅3=????????????
????????????−3+3⋅3
⋯
=????????????
2+
????????????−2⋅3=????????????
1+3+????????????−2⋅3
=????????????
1+
????????????−1⋅3=2+????????????−1⋅3
=3⋅????????????−1
© S. Turaev, CSC 1700 Discrete Mathematics 8

9. Recurrence Relations : Backtracking
Example 1: ????????????
????????????=5????????????
????????????−1+3, ????????????
1=3.
Example 2:????????????
????????????=????????????
????????????−1+????????????, ????????????
1=4.
Example 3:????????????
????????????=????????????⋅????????????
????????????−1, ????????????
1=6.
© S. Turaev, CSC 1700 Discrete Mathematics 9

10. Fibonacci Numbers
Definition:the Fibonacci sequence, ????????????
0,????????????
1,????????????
2,…,is
defined by:
Initial Conditions: ????????????
0=0,????????????
1=1
Recurrence Relation: ????????????
????????????=????????????
????????????−1+????????????
????????????−2
Example: Find ????????????
4,????????????
5,????????????
6,????????????
7and ????????????
8.
© S. Turaev, CSC 1700 Discrete Mathematics 10

11. Linear Homogeneous Recurrence Relations
Definition: A linear homogeneous recurrence relation of
degree ????????????with constant coefficients is a recurrence
relation of the form
????????????
????????????=????????????
1????????????
????????????−1+????????????
2????????????
????????????−2+⋯+????????????
????????????????????????
????????????−????????????
where ????????????
1,????????????
2,…,????????????
????????????are real numbers, and ????????????
????????????≠0.
© S. Turaev, CSC 1700 Discrete Mathematics
•it is linearbecause the right- hand side is a sum of the previous
terms of the sequence each multiplied by a function of ???????????? .
•it is homogeneous because no terms occur that are not
multiples of the ????????????
????????????s. Each coefficient is a constant.
•the degreeis????????????because ????????????
????????????is expressed in terms of the
previous ????????????terms of the sequence.
11

12. Linear Homogeneous Recurrence Relations
????????????
????????????=1.11????????????
????????????−1
????????????
????????????=????????????
????????????−1+????????????
????????????−2
????????????
????????????=????????????
????????????−1+????????????
????????????−2
2
ℎ
????????????=2ℎ
????????????−1+1
????????????
????????????=????????????????????????
????????????−1
© S. Turaev, CSC 1700 Discrete Mathematics 12

13. Linear Homogeneous Recurrence Relations
????????????
????????????=1.11????????????
????????????−1
????????????
????????????=????????????
????????????−1+????????????
????????????−2
????????????
????????????=????????????
????????????−1+????????????
????????????−2
2
ℎ
????????????=2ℎ
????????????−1+1
????????????
????????????=????????????????????????
????????????−1
© S. Turaev, CSC 1700 Discrete Mathematics
linear homogeneous recurrence
relation of degree 1
linear homogeneous recurrence
relation of degree 2
not linear
not homogeneous
coefficients are not constants
13

14. Linear Homogeneous Recurrence Relations
The basic approach is to look for solutions of the form
????????????
????????????=????????????
????????????
,where ????????????is a constant.
Note that ????????????
????????????=????????????
????????????
is a solution to the recurrence
relation
????????????
????????????=????????????
1????????????
????????????−1+????????????
2????????????
????????????−2+⋯+????????????
????????????????????????
????????????−????????????
if and only if
????????????
????????????
=????????????
1????????????
????????????−1
+????????????
2????????????
????????????−2
+⋯+????????????
????????????????????????
????????????−????????????
.
© S. Turaev, CSC 1700 Discrete Mathematics 14

15. Linear Homogeneous Recurrence Relations
Algebraic manipulation yields the characteristic
equation:
????????????
????????????
−????????????
1????????????
????????????−1
−????????????
2????????????
????????????−2
−⋯−????????????
????????????=0

The sequence ????????????
????????????with ????????????
????????????=????????????
????????????
is a solutionif and
only if ????????????is a solution to the characteristic equation.
© S. Turaev, CSC 1700 Discrete Mathematics 15

16. Linear Homogeneous Recurrence Relations
Theorem: If the characteristic equation
????????????
2
−????????????
1????????????−????????????
2=0
of the recurrence relation ????????????
????????????=????????????
1????????????
????????????−1+????????????
2????????????
????????????−2has two
distinct roots, ????????????
1and ????????????
2, then
????????????
????????????=????????????????????????
1
????????????+????????????????????????
2
????????????
where ????????????and ????????????depend on the initial conditions, is the
explicit formula for the sequence.
© S. Turaev, CSC 1700 Discrete Mathematics 16

17. Linear Homogeneous Recurrence Relations
Theorem: If the characteristic equation
????????????
2
−????????????
1????????????−????????????
2=0
of the recurrence relation ????????????
????????????=????????????
1????????????
????????????−1+????????????
2????????????
????????????−2has a
single root, ????????????, then
????????????
????????????=????????????????????????
????????????
+????????????????????????????????????
????????????
where ????????????and ????????????depend on the initial conditions, is the
explicit formula for the sequence.
© S. Turaev, CSC 1700 Discrete Mathematics 17

18. Linear Homogeneous Recurrence Relations
Example 1: Find an explicit formula for the sequence
defined by ????????????
????????????=4????????????
????????????−1+5????????????
????????????−2with the initial
conditions ????????????
1=2and ????????????
2=6.
Example 2: Find an explicit formula for the sequence
defined by ????????????
????????????=−6????????????
????????????−1−9????????????
????????????−2with the initial
conditions ????????????
1=2.5and ????????????
2=4.7.
Example3 (Fibonacci sequence): Find an explicit formula
for the sequence defined by ????????????
????????????=????????????
????????????−1+????????????
????????????−2with the
initial conditions ????????????
0=0and ????????????
1=1.
© S. Turaev, CSC 1700 Discrete Mathematics 18