Ejemplos

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations
Lucia Moura

Winter 2010

CSI2101 Discrete Structures Winter 2010: Recurrence Relations

Lucia Moura

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Recurrence Relations
A recurrence relation for the sequence{an } is an equation that
expresses an in terms of one or more of the previous terms
a0 , a1 , . . . , an−1 , for all integers n with n ≥ n0 .

CSI2101 Discrete Structures Winter 2010: Recurrence Relations

Lucia Moura

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Recurrence Relations
A recurrence relation for thesequence {an } is an equation that
expresses an in terms of one or more of the previous terms
a0 , a1 , . . . , an−1 , for all integers n with n ≥ n0 .
Many sequences can be a solution for the same recurrence
relation.
an = 2an−1 − an−2 , for n ≥ 2
The following sequences are solutions of this recurrence relation:

CSI2101 Discrete Structures Winter 2010: Recurrence Relations

Lucia MouraRecurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Recurrence Relations
A recurrence relation for the sequence {an } is an equation that
expresses an in terms of one or more of the previous terms
a0 , a1 , . . . , an−1 , for all integers n with n ≥ n0 .
Many sequences can be a solution for the same recurrence
relation.
an = 2an−1− an−2 , for n ≥ 2
The following sequences are solutions of this recurrence relation:
an = 3n, for all n ≥ 0,

CSI2101 Discrete Structures Winter 2010: Recurrence Relations

Lucia Moura

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Recurrence Relations
A recurrence relation for the sequence {an } is an equation thatexpresses an in terms of one or more of the previous terms
a0 , a1 , . . . , an−1 , for all integers n with n ≥ n0 .
Many sequences can be a solution for the same recurrence
relation.
an = 2an−1 − an−2 , for n ≥ 2
The following sequences are solutions of this recurrence relation:
an = 3n, for all n ≥ 0,
an = 5, for all n ≥ 0.

CSI2101 Discrete Structures Winter 2010: Recurrence RelationsLucia Moura

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Recurrence Relations
A recurrence relation for the sequence {an } is an equation that
expresses an in terms of one or more of the previous terms
a0 , a1 , . . . , an−1 , for all integers n with n ≥ n0 .
Many sequences can be a solution for the same recurrencerelation.
an = 2an−1 − an−2 , for n ≥ 2
The following sequences are solutions of this recurrence relation:
an = 3n, for all n ≥ 0,
an = 5, for all n ≥ 0.

The initial conditions for a sequence specify the terms before n0
(before the recurrence relation takes effect).
The recurrence relations together with the initial conditions uniquely
determines the sequence. For the example above, theinitial
conditions are: a0 = 0, a1 = 3; and a0 = 5, a1 = 5; respectively.
CSI2101 Discrete Structures Winter 2010: Recurrence Relations

Lucia Moura

Recurrence Relations

Solving Linear Recurrence Relations

Divide-and-Conquer RR’s

Recurrence Relations

Modeling with Recurrence Relations

(used for advanced counting)

Compound interest: A person deposits $10,000 into savings thatyields 11% per year with interest compound annually. How much is in
the account in 30 years?
Growth of rabbit population on an island:
A young pair of rabbits of opposite sex are placed on an island. A pair
of rabbits do not breed until they are 2 months old, but then they
produce another pair each month. Find a recurrence relation for the
number of pairs of rabbits on the island after n...