Announcements

CS311H: Discrete Mathematics

Recurrence Relations
Instructor: Isl Dillig

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

1/25

In previous lectures, we looked at recursively-defined sequences

Example: What sequence is this?

a0
an

Final exam: Tuesday, December 15, 9-12 pm

Im out of town next Tuesday TAs will hold review session

during class

Recurrence Relations

2/25

Recurrence Relations

= 1
= an1 + 1

Recurively defined sequences are often referred to as

recurrence relations

The base cases in the recursive definition are called initial

values of the recurrence relation

= 1
= 1
= fn1 + fn2

Example: Write recurrence relation representing number of

bacteria in nth hour if colony starts with 5 bacteria and
doubles every hour?

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

3/25

Instructor: Isl Dillig,

Closed Form Solutions

CS311H: Discrete Mathematics

Recurrence Relations

4/25

Closed Form Solutions of Recurrence Relations

Recurrence relations are often very natural to define, but we

usually need to find closed form solution

Recall: Closed form solution defines nth number in the

sequence as a function of n

Example: Closed form solution for arithmetic sequence with

initial term a and common difference d :

Given an arbitrary recurrence relation, is there a mechanical

way to describe the closed form solution?

Not for arbitrary, but for a subclass of recurrence relations

A linear homogeneous recurrence relation with constant

coefficients is a recurrence relation of the form:
an = c1 an1 + c2 an2 + . . . + ck ank

dn(n + 1)
an +
2

where each ci is a constant and ck is non-zero

I

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Another example: Fibonacci numbers

f0
f1
fn

Last homework out today, due to last day of class (Dec 4)

Instructor: Isl Dillig,

Recall: Recursively Defined Sequences

I

CS311H: Discrete Mathematics

Recurrence Relations

Instructor: Isl Dillig,

5/25

The value of k is called the degree of the recurrence relation

CS311H: Discrete Mathematics

Recurrence Relations

6/25

Examples and Non-Examples

Characteristic Polynomial

The recurrence relation fn = fn1 + fn2 for Fibonacci

numbers is linear homogeneous recurrence with degree 2

Which of these are linear homogenous recurrence relations

with constant coefficients?
I

an = an1 + 2an5

an = 2an2 + 5

an = an1 + n

an = an1 an2

an = n an1

Instructor: Isl Dillig,

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

What are the characteristic equations for the following

recurrence relations?
I

fn = fn1 + fn2

an = 2an1

an = 2an1 + 5an3

CS311H: Discrete Mathematics

Recurrence Relations

9/25

Instructor: Isl Dillig,

Recurrence Relations

8/25

The characteristic roots of a linear homogeneous recurrence

relation are the roots of its characteristic equation.

What are the characteristic roots of the following recurrence

relations?
I

an = 2an1 + 3an2

fn = fn1 + fn2

CS311H: Discrete Mathematics

Recurrence Relations

10/25

Find a closed form solution for the recurrence an = an1 + 2an2

with initial conditions a0 = 2 and a1 = 7

Furthermore, given k initial conditions, the constants

1 , . . . , k are uniquely determined
Note: Wont do the proof because requires a good amount of
linear algebra

Recurrence Relations

Example

Then the closed form solution for an is of the form:

CS311H: Discrete Mathematics

CS311H: Discrete Mathematics

Instructor: Isl Dillig,

1 r1n + 2 r2n + . . . + k rkn

Definition: The characteristic equation of a recurrence relation

of the form an = c1 an1 + c2 an2 + . . . ck ank is

Characteristic Roots

Let an = c1 an1 + c2 an2 + . . . + ck ank be a recurrence relation

with k distinct characteristic roots r1 , . . . , rk .

Instructor: Isl Dillig,

7/25

Theorem I for Solving Linear Homogenous Recurrence

Relations

Cook-book recipe for solving linear homogenous recurrence

relations with constant coefficients

r k = c1 r k 1 + c2 r k 2 + . . . + ck

Characteristic Equation Examples

11/25

Characteristic equation:

Characteristic roots:

Coefficients:

Closed-form solution:

Check that the solution really is correct!

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

12/25

Generalized Theorem

An Example

So far, we assume all characteristic roots are distinct what

happens if this is not the case?

Theorem: Let an = c1 an1 + c2 an2 + . . . + ck ank be a

recurrence relation with t distinct characteristic roots
r1 , . . . , rk with multiplicities m1 , . . . , mk . Then solutions are
of the form:
an =

t
X
(i,0 + i,1 n + . . . + i,mi1 n mi 1 )rin
i=0

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

Find closed form of recurrence an = 3an1 3an2 + an3

with initial conditions a0 = 1, a1 = 3, a2 = 7

Characteristic equation:

Characteristic roots:

Solution form:

Coefficients:

Instructor: Isl Dillig,

13/25

Bitstring Example
I

Recurrence relations useful for solving counting problems

how many bitstrings of length n without two consecutive 0s?

Let an denote the number of bitstrings that do not contain

two consecutive 0s.

How do we solve linear, but non-homogeneous recurrence

relations, such as an = 2an1 + 1?

A linear non-homogeneous recurrence relation with constant

coefficients is of the form:

Write a recurrence relation for an :

Initial conditions:

Question: Find closed form solution for an

14/25

Characteristic roots:

an = c1 an1 + a2 an2 + . . . + ck ank + F (n)

I

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

Instructor: Isl Dillig,

15/25

Particular Solution

The recurrence obtained by dropping F (n) is called the

associated homogeneous recurrence relation

CS311H: Discrete Mathematics

Recurrence Relations

16/25

Theorem about Linear Non-homogeneous Recurrences

Suppose an = c1 an1 + . . . + ck ank + F (n) has particular
solution anp , and anh is solution for associated homogeneous
recurrence. Then every solution is of the form anp + anh .

A particular solution for a recurrence relation is one that

satisfies the recurrence but not necessarily the initial
conditions

Example: Consider the recurrence an = an1 + 1 with initial

condition a0 = 5

A particular solution for this recurrence is an = n, but it does

not satisfy the initial condition

CS311H: Discrete Mathematics

Recurrence Relations

Proof: Since anp is a particular solution, it satisfies:

p
p
anp = c1 an1
+ . . . + ck ank
+ F (n)

If bn is another solution, it must also satisfy:

bn = c1 bn1 + . . . + ck bnk + F (n)

Instructor: Isl Dillig,

Recurrence Relations

Solving Linear Non-Homogeneous Recurrence Relations

CS311H: Discrete Mathematics

17/25

Instructor: Isl Dillig,

But bn anp is a solution of the homogeneous recurrence

relation; hence every solution is of the form anp + anh

CS311H: Discrete Mathematics

Recurrence Relations

18/25

Why is this theorem useful?

How do we find a particular solution?

Theorem: Consider an = c1 an1 + . . . + ck ank + F (n) where:

If we can find a particular solution, then we can also

mechanically find a solution that satisfies initial conditions.

Example: Solve the recurrence relation an = 3an1 + 2n with

initial condition a1 = 3

A particular solution: n

Solutions for homogeneous recurrence:

Solutions for recurrence:

Solve for :

3
2

F (n) = (bt n t + bt1 n t1 + . . . + b1 n + b0 )s n

Case 1: If s is not a root of the associated characteristic

equation, then there exists a particular solution of the form:

(Why?)

(pt n t + pt1 n t1 + . . . + p1 n + p0 )s n
I

Case 2: If s is a root with multiplicity m of the characteristic

equation, then there exists a solution of the form:
n m (pt n t + pt1 n t1 + . . . + p1 n + p0 )s n

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

19/25

Instructor: Isl Dillig,

Example I

CS311H: Discrete Mathematics

Consider again the recurrence an = 3an1 + 2n

Here, s = 1 and characteristic root is 3

Hence, there exists a particular solution of the form p1 n + p0

Now, solve for p0 , p1 :

p1 n + p0 = 3(p1 (n 1) + p0 ) + 2n

Find a particular solution for an = 6an1 9an2 + 2n

Characteristic root:

Particular solution of the form:

Find p0 such that p0 2n = 6(p0 2n1 ) 9(p0 2n2 ) + 2n

Rearrange: 2n(p1 + 1) + (2p0 3p1 ) = 0

Solve for p0 :

A solution p1 = 1, p0 = 32

Particular solution:

A particular solution: n

3
2

CS311H: Discrete Mathematics

Recurrence Relations

21/25

Instructor: Isl Dillig,

Towers of Hanoi

CS311H: Discrete Mathematics

Recurrence Relations

22/25

A Recursive Solution

Given 3 pegs where first peg contains n disks

Goal: Move all the disks to a different peg (e.g., second one)

Rule 1: Larger disks cannot rest on top of smaller disks

Rule 2: Can only move the top-most disk at a time

Question: How many steps does it take to move all n disks?

Instructor: Isl Dillig,

20/25

Example II

Instructor: Isl Dillig,

Recurrence Relations

CS311H: Discrete Mathematics

Recurrence Relations

23/25

Solve recursively Tn is number of steps to move n disks

Base case: n = 1, move disk from first peg to second: T1 = 1

Induction: Suppose we can move n 1 disks in Tn1 steps;

how many steps does it take to move Tn disks?

Idea: First move the topmost n 1 disks to peg 3; can be

done in Tn1 steps

Now, move bottom-most disk to peg 2 takes just 1 step

Finally, recursively move n 1 disks in peg 3 to peg 2 can

be done in Tn1 steps

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

24/25

Towers of Hanoi, cont.

I

Recurrence relation:

Initial condition:

Now find closed form for Tn

What is a particular solution?

Solution for homogeneous recurrence:

Solve for :

Solution for recurrence:

Instructor: Isl Dillig,

CS311H: Discrete Mathematics

Recurrence Relations

25/25