Transcript Chapter 10 Recurrence relations

Chapter 10
Recurrence relations
Yen-Liang Chen
Dept of Information Management
National Central University
10.1 The first-order linear
recurrence relation

The equation an+1=3an is a recurrence
relation with constant coefficients. Since an+1
only depends on its immediate predecessor,
the relation is said to be first order. The
expression a0=5 is referred to as an initial
condition.
 The unique solution of the recurrence
relation an+1=dan, where n1 and a0=A, is
given by an=Adn.
Examples

Ex 10.1, Solve the recurrence relation an=7an-1,
where n1 and a2=98.
– Assume the solution as an=A7n.

Ex 10.2. A bank pay 6% annual interest on saving,
compounding the interest monthly. If we deposit
$1000 on the first day of May, how much will this
deposit be worth a year later?
– pn+1=(1.005)pn, p0=1000, and we seek for p12
Ex 10.3.

Let an denote the number of compositions of n, we find that
an+1=2an, n1, a1=1
Tips

The recurrence relation an+1=dan is called
linear because each term appears to the first
power. Sometimes a nonlinear recurrence
relation can be transformed to a linear one by
a suitable algebraic substitution.
 Ex 10.4. Find a12 if an+12=5an2 for n0 and
a0=2.
– Let bn=an2. Then bn+1=5bn for n0 and b0=4.
homogeneous and nonhomogeneous

The general first-order linear recurrence
relation with constant coefficients has the
form an+1+c an=f(n). When f(n)=0, the relation
is called homogeneous. Otherwise, it is called
nonhomogeneous.
 Ex 10.5. Bubble sort. Let an denote the
number of comparisons needed to sort n
numbers in this way, we find that
– an=an-1+(n-1) , n2, a1=0
Examples

Ex 10.6. an-an-1=2n , n1, a1=0, Finally, we
have an=n2+n.
 Ex 10.7. an=n.an-1, n1, a0=1, Finally, we have
an=n!.
10.2 The second-order linear homogeneous
recurrence relation with constant coefficients






C0an+C1an-1+C2an-2=0, n2.
Substituting an=crn into the equation, we have
C0crn+C1 crn-1 +C2 crn-2 =0, n2.
C0r2+C1 r +C2 =0, n2. characteristic equation
The roots r1, r2 of this equation are called
characteristic roots.
Three cases for the roots: (1) distinct real
roots, (2) repeated real roots, (3) complex
roots
Ex 10.9.






Solve the recurrence relation an+an-1-6an-2=0, n2,
and a0=-1 and a1=8
r2+r-6=0  r=2, -3
an=c1(2)n+c2(-3)n
-1=a0=c1+c2
8=a1=2c1-3c2c1=1, c2=-2
 an=(2)n-2(-3)n
Ex 10.10.

Fn+2=Fn+1+Fn, n0, F0=1, F1=1
 Let Fn=crn.
 r2-r-1=0
 r=(1(5)0.5)/2
Ex 10.11.






For n0, let S={1, 2, …, n}, and let an denote
the number of subsets of S that contains no
consecutive integers.
a0=1 and a1=2 and a2=3 and a3=5
If AS and A is to be counted in an, there are
two cases
(1) nA, then A-{n} would be counted in an-2
(2) nA, then A would be counted in an-1
an=an-1+an-2, n2
Ex 10.12.

Suppose we have a 2n chessboard. We
wish to cover such a chessboard using
21 vertical dominoes or 12 horizontal
dominoes.
Ex 10.12






let bn denote the number of ways we can cover a 2n
chessboard by using 21 vertical dominoes or 12
horizontal dominoes.
b1=1 and b2=2
For n3, consider the last column of the chessboard
(1) By one 21 vertical domino, bn-1
(2) By two 12 horizontal dominoes, place one
above the other. bn-2
bn=bn-1+bn-2, n3
Ex 10.14.







Suppose the symbols of computation include 0, 1,…,
9, +, *, /.
Let an be the number of these expressions that are
made up of n symbols.
a0=0 and a1=10 and a2=100
For n3, consider the two cases.
(a) If x is an expression of n-1 symbols, the last
symbol must be a digit. 10an-1
(b) If x is an expression of n-2 symbols, we adjoin to
the right of x one of the 29 two-symbol expression
+0, …,+9, *0, …, *9, /1, /2,…, /9. 29an-2
an=10an-1+29an-2, n3
Ex 10.15.



palindromes are the compositions of numbers that
read the same left to right as right to left. Figure
10.6
Let pn denote the number of palindromes of n.
pn=2pn-2, n3, p1=1, p2=2
Ex 10.16.

Find the number of recurrence relation for the
number of binary sequences of length n that have no
consecutive 0’s.
 Let an be the number of such sequences of length n.
 Let an(0) count those end in 0, and an(1) count those
end in 1.
 If x ends in 1, we can append a 0 or a 1 to it (2an-1(1)).
 If x ends in 0, we can append a 1 to it (an-1(0)).
 an=2an-1(1)+ an-1(0)
 Note that sequence y is counted in an-2  sequence
y1 is counted in an-1(1)
 Consequently, an-2= an-1(1).
 an=an-1+ an-2, n3, a1=2, a2=3
second order or higher order
recurrence relation






Ex 10.18.
2an+3=an+2+2an+1-an, n0, a0=0, a1=1, a2=2
Let an=crn
2r3-r2-2r+1=0r=1, 1/2, -1
an=c1(1)n+c2(-1)n+c3(1/2)n
an=(5/2)+(1/6)(-1)n+(-8/3)(1/2)n
Ex 10.19.

Suppose we have a 2n chessboard. We
wish to cover such a chessboard using two
types of tiles shown in Figure 10.8.
Ex 10.19







let an denote the number of ways we can cover a 2n
chessboard.
a1=1 and a2=5 and a3=11
For n4, consider the last column of the chessboard
(a) the nth column is cover by two 11 tiles. an-1
(b) the (n-1)st and the n-th column are covered by
one 11 tile along with a larger tile. 4an-2
(c) the (n-2)nd, (n-1)st and the nth columns are cover
by two large tiles. 2an-3
an=an-1+4an-2+2an-3, n4
Important formula
(cos + i sin )n=cos n+ i sin n
 Ex.10.21

– Solve the recurrence relation an=2(an-1-an-2)
for n2, a0=1, a1=2
– Let an=crn
– r2-2r+2=0r=1i
– 1+i=(2)0.5(cos(/4)+i sin(/4))
– 1-i=(2)0.5(cos(/4)-i sin(/4))
Ex 10.22.

Let an denote the value of the nn
determinant Dn
 a1=b, a2=0 and a3=-b3
 Dn=bDn-1-b2Dn-2
 an=ban-1-b2an-2
Ex 10.23.
Solve
the recurrence relation an+2=4an+1-4an
for n2, a0=1, a1=3
Let an=crn
r2-4r+4=0r=2
Let an=cnrn
r2-4r+4=0r=2
an=c12n+c2n2n
an=2n+(1/2)n2n
Important tips

In general, if
C0an+ C1an-1+ C2an-2 +…+ Ckan-k=0
with r a characteristic root of multiplicity m,
then the part of the general solution that
involves the root r has the form
A0rn+ A1nrn+A2n2rn+ A3n3rn+…+ Am-1nm-1rn
Ex 10.24.
pn=pn-1-(.25)pn-2, for n2
 Let pn=crn
 r2-r+(1/4)=0r=1/2
 pn=(c1+c2n)(1/2)n

10.3 The nonhomogeneous
recurrence relation

an+C1an-1=f(n), n1, an+C1an-1+C2an-2=f(n),
n2
 Let an(h) denote the general solution of the
associated homogeneous relation.
 Let an(p) denote a solution of the given
nonhomogeneous relation. (particular solution)
 Then an= an(h)+ an(p) is the general solution of
the problem.
Ex 10.26.

Solve the recurrence relation
an-3an-1=5(7n) for n1 and a0=2.
The solution for an-3an-1=0 is an(h)=c(3n).
 (Let an(p)=A7n) The particular solution for an3an-1=5(7n) is an(p)=(5/4)7n+1.
 The solution to the problem is an= c(3n)+
(5/4)7n+1
 Finally, we have an= (1/4)(3n+3)+ (5/4)7n+1

Ex 10.27.
Solve the recurrence relation an-3ann) for n1 and a =2.
=5(3
1
0
 The solution for an-3an-1=0 is an(h)=c(3n).
 (Let an(p)=Bn3n) The particular solution
for an-3an-1=5(3n) is an(p)=(5)n3n+1.
 The solution to the problem is an=
c(3n)+ (5)n3n+1
 Finally, we have an= (2+5n)(3n)

Method for the first order relation
an+C1an-1=krn.
 If rn is not a solution of the
homogeneous relation an+C1an-1=0,
then an(p)=Arn.
 If rn is a solution of the homogeneous
relation, then an(p)=Bnrn.

Method for the second order relation
an+C1an-1+C2an-2=krn.
 If rn is not a solution of the
homogeneous relation an+C1an-1+
C2an-2=0, then an(p)=Arn.
 If an(h)=c1rn+c2r1n, where rr1, then
an(p)=Bnrn.
 If an(h)=(c1+c2n)rn, then an(p)=Cn2rn.

Ex 10.29.

Let an denote the amount still owed on the loan at the
end of the nth period.
 an+1=an+ran-P, 0nT-1, a0=S, aT=0
 The solution for an+1=an+ran is an(h)=c(1+r)n.
 (Let an(p)=A) The particular solution for an+1=an+ran-P
is an(p)=P/r.
 The solution to the problem is an= c(1+r)n + P/r
 Finally, we have an= (S-(P/r))(1+r)T+(P/r)
 Since 0=aT, we have P=(Sr)[1-(1+r)-T]-1
Ex 10.30.
Let S be a set containing 2n real
numbers. We want to find the maximum
and minimum from S. Let an denote the
number of comparisons we made for 2n
data.
 an+1=2an+2, n1.

Ex 10.31





For the alphabet={0,1,2,3}, how many strings
of length n contains an even number of 1’s.
Consider the nth symbol of a string of length
n
(1) The nth symbol is 0, 2, 3. 3an-1
(2) The nth symbol is 1. Then there must be
an odd number of 1’s among the first n-1
symbols. 4n-1-an-1
an=3an-1+(4n-1-an-1)=2 an-1+4n-1
Ex 10.32.





Snowflake curve shown in Figure 10.12. P0, P1, P2
Let an denote the area of the polygon Pn obtained
from the original equilateral triangle after we apply
n transformations.
a0=(3)0.5/4
a1=(3)0.5/4+(3) [(3)0.5/4](1/3)2=(3)0.5/3
a2=(3)0.5/3+(4)(3) [(3)0.5/4][(1/3)2]2=10(3)0.5/27
Ex 10.34.





Solve the recurrence relation an+2-4an-1+3an=200 for n0 and a0=3000 and a1=3300.
The solution for an+2-4an-1+3an=0 is
an(h)=c1(3n)+c2.
(Let an(p)=An) The particular solution for an+24an-1+3an=-200 is an(p)=100n.
The solution to the problem is an=
c1(3n)+c2+100n
Finally, we have an= 100(3n)+2900+100n
Ex 10.35.
Two programs in Figure 10.15. Which
one is more efficient?
 an=an-1+an-2+1
 n-1

How to set the particular solution?
(1) If f(n) is a constant multiple of one of the forms in
the first column of Table 10.2.
(2) When f(n) comprises a sum of constant multiples of
terms.
For example, if f(n)=n2+3 sin 2n, then
an(p)=(A2n2+A1n+A0)+(A sin 2n+ B cos 2n)
(3) If a summand f1(n) is a solution of the associated
homogeneous relation.
If f1(n) causes this problem, we multiply the trial
solution (an(p))1 corresponding to f1(n) by the
smallest power of n, say ns, for which no summand
of ns f1(n) is a solution of the associated
homogeneous relation. Thus, ns(an(p))1 is the
corresponding part of an(p).
Ex 10. 36.

an+1=an+n, n2, a2=1
 The solution for an+1=an-1 is an(h)=c(1n)=c.
 Let an(p)=A1n+A0.
 By the reasons stated above, let an(p)=A1n2+A0n
 The particular solution for an+1=an+n is an(p)=(1/2)n2+(1/2)n.
 The solution to the problem is an= c+(1/2)n2+(-1/2)n
 Finally, we have an=(1/2)n(n-1)
Ex 10.37.

an+2-10an+1+21an=f(n), n0
 an(h)=c1(3n)+c2(7n).
10.4 The method of generating
functions

Ex 10.38. Solve the relation an-3an-1=n,
n1, a0=1.

n
a
x
 Let f(x)=  n
be the generating function
0
for a0, a1n,…,
an.
Ex 10.39.

Solve the relation an+2-5an+1+6an=2, n0,
a0=3, a1=7.

n
 Let f(x)=  an x be the generating function
n 0
for a0, a1,…, an
Ex 10.40.
Let a(n, r) be the number of ways we
can select, with repetitions allowed, r
objects from a set of n distinct objects.
 Then a(n, r)=a(n-1, r)+a(n, r-1).
 Let fn=  a(n, r ) x be the generating
function for a(n, 0), a(n, 1), a(n, 2),…,


r
r 0
10. 5. A special kind of nonlinear
recurrence relation

Ex 10.42. Let bn denote the number of
rooted ordered binary trees on n nodes.
 b3=5 is shown in Figure 10.18.
 bn+1=b0bn+ b1bn-1+…+ bn-1b1+ bnb0
 Let f(x)= be the generating function for b0,
b1,…, bn.
10.6 Divide-and-conquer algorithms

f(1)=c
f(n)=af(n/b)+h(n) for n=bk
 Theorem 1
Ex 10.45

(a) f(1)=3 and f(n)=f(n/2)+3 for n=2k
– c=3, b=2, a=1
– f(n)=3(log2n+1)

(b) g(1)=7 and g(n)=4g(n/3)+7 for n=3k
– c=7, b=3, a=4
– g(n)=(7/3)(4nlog34-1)

(c) h(1)=5 and h(n)=7h(n/7)+5 for n=7k
– c=5, b=7, a=7
– h(n)=(6/5)(7n-1)
Definition 10.1

g dominates f on S if there is a constant
m such that f(n) m g(n)for all nS.
We say that fO(g) on S.
 Ex 10.46, Ex 10.47
 Corollary 10.1
Corollary 10.2
Theorem 10.2