Report

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=3an 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=dan, where n1 and a0=A, is given by an=Adn. Examples Ex 10.1, Solve the recurrence relation an=7an-1, where n1 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, n1, a1=1 Tips The recurrence relation an+1=dan 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 n0 and a0=2. – Let bn=an2. Then bn+1=5bn for n0 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) , n2, a1=0 Examples Ex 10.6. an-an-1=2n , n1, a1=0, Finally, we have an=n2+n. Ex 10.7. an=n.an-1, n1, 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, n2. Substituting an=crn into the equation, we have C0crn+C1 crn-1 +C2 crn-2 =0, n2. C0r2+C1 r +C2 =0, n2. 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, n2, 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-3c2c1=1, c2=-2 an=(2)n-2(-3)n Ex 10.10. Fn+2=Fn+1+Fn, n0, F0=1, F1=1 Let Fn=crn. r2-r-1=0 r=(1(5)0.5)/2 Ex 10.11. For n0, 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 AS and A is to be counted in an, there are two cases (1) nA, then A-{n} would be counted in an-2 (2) nA, then A would be counted in an-1 an=an-1+an-2, n2 Ex 10.12. Suppose we have a 2n chessboard. We wish to cover such a chessboard using 21 vertical dominoes or 12 horizontal dominoes. Ex 10.12 let bn denote the number of ways we can cover a 2n chessboard by using 21 vertical dominoes or 12 horizontal dominoes. b1=1 and b2=2 For n3, consider the last column of the chessboard (1) By one 21 vertical domino, bn-1 (2) By two 12 horizontal dominoes, place one above the other. bn-2 bn=bn-1+bn-2, n3 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 n3, 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, n3 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, n3, 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, n3, a1=2, a2=3 second order or higher order recurrence relation Ex 10.18. 2an+3=an+2+2an+1-an, n0, a0=0, a1=1, a2=2 Let an=crn 2r3-r2-2r+1=0r=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 2n 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 2n chessboard. a1=1 and a2=5 and a3=11 For n4, consider the last column of the chessboard (a) the nth column is cover by two 11 tiles. an-1 (b) the (n-1)st and the n-th column are covered by one 11 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, n4 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 n2, a0=1, a1=2 – Let an=crn – r2-2r+2=0r=1i – 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 nn 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 n2, a0=1, a1=3 Let an=crn r2-4r+4=0r=2 Let an=cnrn r2-4r+4=0r=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 n2 Let pn=crn r2-r+(1/4)=0r=1/2 pn=(c1+c2n)(1/2)n 10.3 The nonhomogeneous recurrence relation an+C1an-1=f(n), n1, an+C1an-1+C2an-2=f(n), n2 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 n1 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 n1 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 rr1, 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, 0nT-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, n1. 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 n0 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, n2, 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), n0 an(h)=c1(3n)+c2(7n). 10.4 The method of generating functions Ex 10.38. Solve the relation an-3an-1=n, n1, 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, n0, 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 nS. We say that fO(g) on S. Ex 10.46, Ex 10.47 Corollary 10.1 Corollary 10.2 Theorem 10.2