Transcript document

Section 6.1
Recurrence Relations
1
Recursive definition of a
sequence
• Specify one or more initial terms
• Specify rule for obtaining subsequent terms
from preceding terms
• We can use such definitions to solve
counting problems that cannot easily be
solved using techniques from chapter 4
2
Recurrence Relations
• When rule for finding subsequent terms from
previous is used for solving counting problems,
we call the rule a recurrence relation
• Stated more formally: A recurrence relation for
the sequence {an} is an equation that expresses
an in terms of one or more of the previous terms
of the sequence a0, a1, … an-1 for all integers n
with nn0, where n0 is non-negative
3
Solutions
• A sequence whose terms satisfy a
recurrence relation is called a solution of the
recurrence relation
• Example 1: Let {an} be a sequence that
satisfies the recurrence relation an = an-1- an-2
for n = 2, 3, 4 …
– Suppose a0=3 and a1=5. What are a2 and a3?
– a2 = a1 - a0 = 2, a3 = a2 - a1 = -3
4
Example 2
• Find the first 5 terms of a sequence defined
as follows:
– recurrence relation: an = nan-1 + n2an-2
– initial condition: a0 = 1, a1 = 1
• Applying the rules:
a2 = 2(1) + (2)21 = 6
a3 = 3(6) + (3)21 = 27
a4 = 4(27) + (4)26 = 204
5
Example 2
• Determine whether {an} is a solution of the
recurrence relation an = 2an-1-an-2 for n=2, 3,
4 … where an = 3n
if an = 3n, then for n  2:
2an-1 - an-2 = 2[3(n-1)] - 3(n-2)
= 2(3n - 3) - 3n + 6
= 6n - 6 - 3n + 6 = 3n
So {an}, where an = 3n, is a solution
6
Example 3
• Determine whether {an} is a solution of the
recurrence relation an = 2an-1-an-2 for n=2, 3,
4 … where an = 2n:
– By this rule, a0 = 20 = 1; a1 = 21 = 2; a2 = 22 = 4
– Applying original recurrence relation:
an = 2a n-1 - a n-2
a2 = 2a1 - a0 substituting actual values:
4 = 2*2 - 1
4 = 3 not true, so {an} where an = 2n is not a solution
7
Summary of Recurrence Relations
• Initial conditions for a sequence specify terms that
precede the first term where recurrence relation
takes effect
• Recurrence relation & initial conditions uniquely
determine a sequence, providing a recursive
definition of the sequence
• Any term of a sequence can be found from initial
conditions using recurrence relation a sufficient
number of times (but there are better ways for
computing certain classes of sequences)
8
Example 4: modeling with
recurrence relations
• Suppose you invest $1,000 in a money market
account that yields 7% per year (wow!) with
interest compounded annually (oh). How much
money will be in the account in 25 years?
– Let Pn = amount in account after n years
– Since Pn = amount after n-1 years + interest in
nth year, {Pn} satisfies the recurrence relation:
Pn = Pn-1 + .07(Pn-1) = 1.07(Pn-1)
9
Example 4 continued
• We are given P0 = 1000; so
P1 = (1.07)(P0)
P2 = (1.07)(P1) = (1.07)(1.07)(P0) = (1.07)2(P0)
P3 = (1.07)(P2) = (1.07)(1.07)(1.07)(P0) = (1.07)3(P0)
… thus Pn = 1.07(Pn-1) = (1.07)nP(0)
so if n=25,
P25 = (1.07)25(1000) = $5,427.43
10
Example 5: is Fibonacci Italian
for “bunny”?
• Suppose 2 baby rabbits (aw!), a buck and a doe,
are placed on an uninhabited island
• They don’t breed until they’re 2 months old (we
don’t know what they’re up to before that)
• After they are 2 months old, each pair of rabbits
produces another pair each month
• How many rabbits are there after n months,
assuming no rabbits die?
11
Example 5 continued
• Let fn = number of rabbit pairs after n
months
• At end of first month, f1 = 1 (too young to
breed)
• At end of second month, f2 = 1 (allow for
gestation time!)
12
Example 5 continued
• To find the number of pairs after n months,
add the number from the previous month
(fn-1) to the number of newborn pairs (fn-2,
since each newborn pair comes from a pair
at least 2 months old)
• So {fn} satisfies the recurrence relation:
fn = f n-1 + f n-2 for n  3 with f1 = f2 = 1
• So the number of pairs of bunnies after n
months is the nth Fibonacci number
13
Example 6: how long before the
world ends?
• The Towers of Hanoi is an ancient puzzle,
with the following characteritics:
– You start with 3 pegs, one of which has a stack
of disks on it (bird’s-eye view shown)
– The disks are stacked by size, with the largest
on the bottom and the smallest on top
14
Example 6 continued
• The goal is to move all disks to a second
peg in order of size
– Only one disk may be moved at a time
– A larger disk can never be placed on top of a
smaller disk
• Let Hn = number of moves needed to solve
a puzzle with n disks; set up a recurrence
relation for sequence {Hn}
15
Example 6 continued
• Starting with n disks on peg 1, we can transfer
n-1 disks to peg 3 using Hn-1 moves
– It takes 1 move to transfer the largest disk to peg 2
– Then we can move the n-1 disks from peg 3 to peg
2 using another Hn-1 additional moves
– So Hn = 2(Hn-1) + 1 with initial condition H1 = 1
(one disk can be transferred in one move)
16
Example 6 continued
• We can use an iterative approach to solve the relation:
Hn = 2(Hn-1) + 1
= 2 (2Hn-2 + 1) = 22Hn-2 + 2 + 1
= 22(2Hn-3 + 1) + 2 + 1 = 23Hn-3 + 22 + 2 + 1
…
= 2n-1H1 + 2n-2 + 2n-3 + … + 2 + 1
= 2n-1 + 2n-2 + 2n-3 + … + 2 + 1 (because H1 = 1)
= 2n - 1
• So for 5 disks, it takes 25-1 or 31 moves to solve the
puzzle
17
Example 6 continued
• The ancient legend says that the monks of Hanoi
must solve a puzzle with 64 disks, taking 1 second
to move each disk, and when they are finished the
world will end. How long before they’re done?
– 264 - 1 = 18,446,744,073,709,551,615 seconds
– At 60 seconds per minute, 60 minutes per hour, 24
hours per day and 365.25 days per year, there are
31,557,600 seconds in a year
– So the world should end something over 500 billion
years since they started (but we don’t know when they
started …)
18
Example 7
• Find a recurrence relation and give initial conditions
for the number of bit strings of length n that do not
have consecutive 0s. How many such strings are there
of length 5?
– Let an denote the number of bit strings of length n that do
not have 2 consecutive 0s; to obtain recurrence relation for
{an}, note that:
• by the sum rule, the # of bit strings of length n that do not have 2
consecutive 0s = # ending with 0 + # ending with 1
• assuming n  3, bit string has at least 3 bits
19
Example 7 continued
• Bit strings of length n ending with 1 that do not have 2
consecutive 0s are precisely the bit strings of length n1 with no 2 consecutive 0s and with a 1 added to the
end - there are an-1 such bit strings
• Bit strings of length n ending with a 0 must have a 1 as
their (n-1)th bit (otherwise there’d be 2 0s at the end) bit strings of length n, ending with 0, without
consecutive 0s, are precisely those bit strings of length
n-2 with 10 appended to them - there are an-2 such
strings
20
Example 7 continued
• So we conclude:
an = an-1 + an-2 for n  3
Initial conditions:
a1 = 2 since bit strings of length 1 have no
consecutive bits and there are 2 possible values
a2 = 3 since valid strings are 01, 11, 10
• a5 = a4 + a3; a4 = a3 + a2; a3 = a2 + a1
– a3 = 5; a4 = 8; so a5 = 13
21
Catalan numbers
• The number of ways to parenthesize the
product of n+1 numbers to specify the order
of multiplication is represented by Cn
• For example, C3 = 5; since n=3, there are 4
terms: x0 * x1 * x2 * x3 and 5 ways to
parenthesize:
(x0 * x1) * (x2 * x3), ((x0 * x1) * x2) * x3,
(x0 * (x1 * x2)) * x3, x0 * ((x1 * x2) * x3) and
x0 * (x1 * (x2 * x3))
22
Catalan numbers
• However we insert parentheses, one
multiplication operator remains outside all
parentheses (and is therefore the last
operation performed)
• The final operator appears between some
pair of the n+1 numbers - say xk and xk+1
23
Catalan numbers
• There are CkCn-k-1 ways to insert
parentheses to determine order of
multiplication of n-1 numbers when the
final operator appears between xk and xk+1
because there are Ck ways to insert
parentheses in x0*x1*…*xk and Cn-k-1 ways
to insert parentheses in xk+1*xk+2*… *xn
24
Catalan numbers
• Since the final operator can appear between
any 2 of the n+1 numbers, it follows that:
Cn = C0Cn-1 + C1Cn-2 + … + Cn-2 C1 + Cn-1C0 =
CkC n-k-1 with initial conditions C0=1, C1=1
• It can be shown that Cn = C(2n,n)/(n+1)
25
Section 5.1
Recurrence Relations
26