10 Recurrence Relations n earlier sections of the text we saw some recursive definitions and constructions. In Definitions 5.19, 6.7, 6.12, and 7.9, we obtained concepts at level x + I (or of size m + 1) from comparable concepts at level 1 (or of size n), after establishing the concept at a first value of n, such as 0 or L. When we dealt with the Fibonacci and Lucas numbers in Section 4.2, the results at level m + 1 tumed out to depend on those at levels n and n — 1; and for each of these sequences of integers the basis consisted of the first two integers (of the sequence). Now we shall find ourselves in a somewhat similar situation. We shall investigate funetions a(n), preferably written as ay (For n = 0), where dg depends on some Of the prior terms yt, dq-2, ~~» i> do, This study of what are called either recurrence relations or difference equations is the diserete counterpart to ideas applied in ordinary differential equations. Our development will not employ any ideas from differential equations but will star with the notion of a geometric progression. AS further ideas are developed, we shall see ‘some of the many applications that make this topic so important, 101 The First-Order Linear Recurrence Relation A geometric progression is an infinite sequence of numbers, such as 5, 15, 45, 135, where the division of each term, other than the first, by its immediate predecessor is a constant, called the common ratio, For our sequence thiscommon ratiois 3: IS = 3(5), 4 3(15), and so on. If ay, a, a2, .. 8a geometric progression, then ay /ay = as/a asi /a =r, the common ratio. In our particular geometric progression we have nt = By. 2 0. The recurrence relation dy.) = 3aq,n > 0, does not define a unique geometric progres- sion. The sequence 7, 21, 63, 189, ... also satisfies the relation. To pinpoint a particular sequence described by dei ~ 3dq, We need to know one of the terms of that sequence. Hence apt = 3dq, 20, uniquely defines the sequence 5, 15, 45, .... whereas Oust = Btu BO = 2, identifies 7, 21, 63, ...as the geometric progression under study. 4a74AB Chapter 10 Recurrence Relations [EXAMPLE 10.1. | EXAMPLE 10.2 ‘The equation ay) ~ Jaq, m > 0 is a recurrence relation because value of ag. (the present consideration) is dependent on ay (a prior consideration). Since ay, depends only fon its immediate predecessor, the relation is said to be of first order. Ia particular, this isa first-order linear homogeneous recurrence relation with constant coefficients. (We'll say more about these ideas later.) The general form of such an equation can be written ps1 = day, 0, where d is a constant ‘Values such as ap oF i, given in addition to the recurrence relations, are called boundary conditions. The expression a ~ A, where A is a constant, is also referred to as an initial condition. Our examples show the importance ofthe boundary condition in determining the “unique solution. Let us return now to the recurrence relation nyt 3,220, a = 5, ‘The first four terms of this sequence are ay = 5. a; = Bap = 315), 3a) = 38ap) = 35), and 33%S)) = 3°) ay = 3a These results suggest that for each n > 0, dy = 5(3"), This is the «nique solution of the given recurrence relation. In this solution, the value of a, is a function of n and there is no longer any dependence on prior terms of the sequence, once we define ay, To compute 4p, for example, we simply calculate 5(3!) = 295,245; there is no need to start ata and build Lup (as in order to obtain a. From this example we are directed to the following, (This result can be established by the Principle of Mathematical Induction.) ‘The unique solution of the recurrence relation Gea = day, wheren 0, dis aconstant, and ay =A, is given by a= Ad", n=O. ‘Thus the solution a, = Ad", n = 0, defines a diserete function whose domain is the set N of all nonnegative integers Solve the recurrence relation dy = Tay 1, Where n > I and a = 98 This is just an alternative form of the relation i. = 7a, for n = Oand as the solution has the form ay = dg(?"). Since ay = 98 = ay(7"), it Follows that ay = a, = 2(7"),n > O, is the unique solution. A bank pays 6% (annual) interest on savings, compounding the interest monthly. If Bonnie deposits $1000 on the first day of May, how much will this deposit be worth a year later? ‘The annual interest rate is 6%, so the monthly rate is 6%%/12 = 0.5% = 0.005. For O 0) to this recur rence relation, we let b dy. Then We have Batt = 2b, M20, by 80 by = bo(2") = 2", and dy = The recurrence relation ayy ~ day = 0 is called linear because each subsctipted term appears to the fist power (a do the variables x and y inthe equation ofaline nthe plane). In a linear relation there are no produets such as y—1, Which appears in the nonlinear recur. rence relation yy ~ 3aud-1 = 0, However, here are times when a nonlinear recurrence relation can be transformed ino a linear one by a suitable algebraic substitution, Find ays if a3, ~ Sa2, where a» O for n > 0, and a Although this recurrence relation is not linear in dy. if we let by ~ a2, then the new relation b,.-) = 5b, form > 0, and by = 4, i linea relation whose solution is by = 4-5 Therefore. dy = 2¢V5) for n> 0, and ais = 24/5)" = 31,250,450 Chapter 10 Recurrence Relations “The general first-order linear recurrence relation with constant coeicents has the form inst + Cay = fn), n= O, where is a constant and fn) is a function on the set N of nonnegative integers ‘When fn) = 0 forall n €N, the relation is called homogeneous; otherwise itis called nonhomogeneous. So far we have only dealt with homogeneous relations. Now we shall solve a nonhomogeneous relation. We shall devclop specific techniques that work for all linear homogencous recurrence relations with constant coefficients. However, many difer- cent techniques prove useful when we deal with a nonhomogeneous problem, although none allows us to solve everything that ean arse EXAMPLE 10.5 Perhaps the most popular, though not the most efficient, method of sorting numeric data isa technique called the bubble sort. Here the input is a positive integer m and an arty 2142, 83. Ty Of reall numbers that are to be sorted into ascending order, “The pseudocode procedure in Fig. 10.2 provides an implementation for an algorithm 10 cary out this sorting process, Here the integer variable ¢ is the counter for the outer for Toop, whereas the integer variable j is the counter for the inner for loop. Finally the real variable temp is used for storage that is needed when an exchange takes place. procedure Bubblesort(n: positive integers x1,%2/%i1..41%, begin for i: 1ten—ide for j :=ndownto i+1do 4fx, 1, we count the total number of comparisons made in ord to sort then siven numbers into ascending order. lay denotes the numberof comparisons needed to sort n numbers inthis way, then we get the following recurrence relation: Oy =F 1), -me2 =O.10.) The First-Order Linear Recurrence Relation ; : 2 % Three comparsons and two interchanges. izalmn 2 Paaaaetry cameis 5 5 aniceeiedicetset] 7 uy, e's SaiceeieMearieis Ornreneg wo comparisons and one terchange aie ee pa eauiiel 5 aang): (One comparison but no interchanges Figure 103 451 This arses as follows. Given a lst of x numbers, we make — 1 comparisons to bubble the smallest number up tothe start ofthe list, The remaining sublist of n = I numbers then requires a, comparisons in order to be completely sorted. ‘This relation isa linear first-order relation with constant coefficients, but the term n — 1 ‘makes it nonhomogeneous, Since we have no technique for attacking such a relation, let us Tist some terms and see whether there is a recognizable pattern, a=0 =a) += 1)=1 ayant 3~ 1) 142 ay =a +4 = 1) 514243 In general, dy = 1424-04 (0-1 [or = nl/2 = 2 =m?452 Chapter 10 Recurrence Relations EXAMPLE 10.6 EXAMPLE 10.7 Asa result, the bubble sort determines the time-complexty function: 2 R given by Ala) = ay = (2? — n)/2. [Here WZ") C N.] Consequently, as a measure of the running Lime for the algorithm, we write © O(a"), Hence the bubble sort is said to require Oca?) comparisons. In pare (c) of Example 9.6 we sought the generating function for the sequence 0, 2, 6, 12, 20, 30, 42, ..., and the solution rested upon our ability to recognize that a, =n? + for each n € N. If we fil to see this, pethaps we can examine the given sequence and determine ‘whether there is some other pattera that will help us Here dy = 0, a1 = 2, a2 = 6, as = 12, ay = 20, as = 30, as = 42, and aay =2 ay az =6 as ay = 10 az—ay 4 aymas=8 aay = 12. These calculations suggest the recurrence relation Gq = ay = 20, n=l, ag =O. To solve this relation, we proceed in a slightly different manner from the method we used in Example 10.5. Consider the following n equations ay = dg = 2 a; a= 4 as ~ a =6 When we add these equations, the sum for the left-hand side will contain a; and ~a; forall 1 Land ay = 1 Writing the first five terms defined by the relation, we hav’ a= leq=t ay Therefore, dy = n! and the solution is the discrete function ay, which counts the number of permutations of 1 objects, n > 0,EXAMPLE 10.8 101. The Fs-Order Linea Recurrence Relation 453, While on the subject of permutations, we shall examine a recursive algorithm for gen- erating the permutations of (1,2, 3,....m — Is) from those for (1. 2.3,.+..1— I) ‘There is only one permutation of {1}, Examining the permutations of (1, 2) 102 aa wwe see that after writing the permutation 1 twice, we intertwine the number 2 about Ito get the permutations listed. Writing each of these two permutations three times, we intertwine the number 3 and obtain 3 3 We see here that the first permutation is 123 and that we obtain each of the next two permutations from its immediate predecessor by interchanging two numbers: 3 and the Integertoits left. When 3 reaches the [eft side of the permutation, we examine the remaining ‘numbers and permute them according to the list of permutations we generated for (1, 2}. (This makes the procedure recursive.) After that we interchange 3 with the integer on its right until 3 is on the right side of the permutation, We note that if we interchange 1 and 2 in the last permutation, we get 123, the first permutation listed. Continuing for $ = (1, 2, 3, 4}, we fist list each of the six permutations of {1, 2, 3} four times. Starting with the permutation 1234, we intertwine the 4 throughout the remaining 23 permutations as indicated in Table 10.1 (on page 454). The only new idea here develops as follows. When progressing from permutation (5) to (6) to (7) to (8), we interchange 4 with the integer to its right, At permutation (8), where 4 has reached the right side, we obtain permutation (9) by keeping the location of 4 fixed and replacing the permutation 132 by 312 from the list of permutations of (1, 2, 3}. After that we continue as forthe first, eight permutations until we reach permutation (16), where 4 is again on the right. We then ppermute 321 to obtain 231 and continue intertwining 4 until all 24 permutations have been generated. Once again, if 1 and 2 are interchanged in the last permutation, we obtain the first permutation in our list. ‘The chapter references provide more information on recursive procedures for generating permutations and combinations. ‘We shall close this first section by returning to an earlier idea—the greatest common divisor of two positive integers. Recursive methods are fundamental in the areas of discrete mathematics and the analysis of algorithms. Such methods arise when we want to solve a given problem by breaking it down, of referring it, to smaller similar problems. In many programming languages this can be implemented by the use of recursive functions and procedures, which are permitted 10 invoke themselves. This example will provide one such procedure, "The material from hereto the end ofthis section is «digression hat ses te idea of ecusion, I doesnot eal with methods fr slving recutence elation ad may be ote with no lew of conn454 Chapter 10 Recurrence Relations Table 101 a 2 @ w 4 4 Oy ON 8) o (10) an «sy (16) an 2 es) en 2 1 * In computing ged(333, 84) we obtain the following calculations when we use the Eur clidean algorithm (presented in Section 4.4), 333=3(84) +81 O<81< 84 o 84-181) 43 O<3<81 a 81= 2708) +0. eo Since 3 is the last nonzero remainder. the Euclidean algorithm tells us that ged(333, 84) = 3. However, if we use only the calculations in Eqs. 2) and (3), then we find that ged(84, 81) = 3. And Eq, (3) alone implies that ged(81, 3) = 3 because 3 divides 81. Consequently, -ged(333, 84) = god(84, 81) = god(81, 3) = 3, ‘where the integers involved in the successive calculations get smaller as we go from Eq. (1) to Eq, 2) 10 Eq, 3). ‘We also observe that 81=333mod 84 and. 3 = 84 mod 81. ‘Therefore it follows that ed(333, 84) = ged(84, 333 mod 84) ~ god(333 mod 84, 84 mod (333 mod 84). ‘These results suggest the following recursive method for computing ged(a, b), where abent Say we have the input a, b € Z* bla (ora mod b = 0), then ged(a, b) If 6a. then perform the following tasks i) Seta) Set b= a mod b, ofa. ) Return to step (1). 101 The First-Order Linear Recurrence Relation 455 Where the value of « for this assignment isthe old value These ideas are used in the pseudocode procedure in Fig. 10.4, (The reader may wish to ‘compare this procedure with the one given ia Fig. 4.1.) procedure ged? (a, b: positive integers) begin Af amed b~ 0 then gcd=b elge ged = ged2\b, a moa b) end Figure 104 1. Find a recurrence relation, with intial condition, that uniquely determines each ofthe following geometric progres- 8) 2, 10,50, 250, by 6, —18, $4, — 162, ©) 7, 14/8, 28/25, 36/125, 2. Find the unique solution foreach of the following recur reace relations 8) gyi ~ 15a, =0, 220 b) 4a, — S01 =0, nz 1 © Baus day =0, 020, ay =5 @) Yay —3de4 = 0, NEN, ay =81 3. ay, 2 0, isthe unique solution of the recurrence rel tion ag) — day © O, and ay = 153/49, as = 1377/2401, what isa? 4. Themumber of acteriaina cultures 1000 (approximately), and this number inereases 250% every two hours, Use a recur rence relation t determine the numberof bacteria present after one day 5. Laura invests $100 at 65% rest compounded quarterly how many months must she wait for her money to double? (She cannot withdraw the money before the quaner is up.) 6, Paul invested the stock profits he received 15 years ago in an account tht paid 8% interest compounded quarterly, I his account now has $7218.27 init, what was hisinitial investment? 7. etx). 25, --- 2 bea list of distinct real numbers to be sorted by the bubble-sort technique of Example 10.5. a) After hos many comparisons willthe 10 smallest numbers ofthe org inal list be arranged in ascending order? (b) How many more comparisons sre needed to finish this sorting job? 8, Forthe implementation of the bubble srt given in Fig. 10.2, the outer for lop is executed n — 1 times. This occurs regard less of whether any interchanges take place during the exe cution of the inner for loop. Consequently, for = &, where 1 sk I,apermutation p:, ps. ps, «+ Pe oftheintegers| 1,2, 3)... is called onderly if, for each # = 1.2.3. Is there existsa j > such that|p, =p! = | [tin = 2,the permutations 1, 2and2, | are bath ondetly. When n= 3 we find that 3, 1, 2s an orderly permutation, while 2,3, 1 isnot. (Why ot?) (a) Lisall the orderly permutations for 1,2, 3.(b)Listall he ordenly pemutations for 1,2, 3, 4.(@) If pr. Bas Pas Pas Ps isan orderly permutation of 1,2. 3,4, 5. what value(s) can be? (d) For n > I, let ay count the number of orderly permu tations for 1, 2. 3... .m. Find and solve a evurtence relation ford,456 Chapter 10. Recurrence Relations 10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients EXAMPLE Let ke Z* and Cy (#0), Ch. Ca... +. Cy (#0) be real numbers. If d,, for n 2 0, is a discrete function, then Cote + Crdant + idea bo + Cetek = fm), nz isa linear recurrence relation (with constant coefficients) of order k. When f(n) = 0 for all n > 0, the relation is called homogeneous; otherwise it is called nonhomogeneous: In this section we shall concentrate on the homogeneous relation of order two: Cita + City t+ Cate 20, 22. (On the basis of our work in Section 10.1, we seek a solution of the form a, = er", where cp Oandr #0, Substituting dy = er" into Cody + Chant + C2ty-2 = 0, we obtain Cyer® + Cer"! + Caer! With c. r # 0, this becomes Cor? + Cyr + C3 = 0, a quadratic equation which is called the characteristic equation. The roots r, r of this equation determine the following three ceases: (a) ri, are distinct real numbers; (b) ri,rz form a complex conjugate pair, or (6) rr ate real, but r) = ra, Im all cases, 7) andr are called the characteristic roots. =0. Case (A): (Distinct Real Roots) Solve the recurrence relation ay + y-1 ~ 6d, Ia, = er" with cr # 0, we obtain or* + cr"! — Ger? teristic equation r? +r — 6 = 0 follows: 0, where n = 2 and a = ~1.a; = 8, 0 from which the charac- O=P+r—6= (+ 3r-Iar Since we have two distinct real 10s, ag = 2" and ay = (~-3)" are both solutions [as are (2") and d(--3)", for arbitrary constants b, dl. They are linearly independent solutions because one is not a multiple of the other; that is, there is no real constant & such that (-3)" = £2") for all n EN.) We waite ay = c4(2") + ex(-3)" for the general solution, Where ¢), c2 are arbitrary constants, With ay = —1 and a = 8, ¢) and cy are determined as follows: 1 ay = 12) bex-3)" = 0 + B= a 12!) + n(—3)" = 2ey — 3c Solving this system of equations. one finds ¢) = I.¢2 = ~2. Therefore. ay = 2" — 2(-3)" rn = 0, s the unique solution of the given recurrence relation. The reader should realize that to determine the unique solution ofa second-order linear homogencous recurrence relation with constant coefficients one needs two initial conditions "We can aso cal the solitons dy = 2" and ax = (3) teary independent when te following canton Is sated Ford) RAT (2") + Aa(—8)" — Oforall = N then ky Hy =OEXAMPLE 10.10 | EXAMPLE 10.11 10.2. The Second-Order Linear Homogeneous Recutrence Relation with Constant Coeficients 457 (values) — that is, the value of a, for two values of n, very often n = Oand n= 1,orn = 1 and n = 2. An interesting second-order homogeneous recurrence relation is the Fibonacci relation (This was mentioned earlier in Sections 4.2 and 9.6.) Solve the recurrence relation Fna3 = Fyyy + Fao where n = Oand Fy =0, F) =1 ‘Asin the previous example, let Fy ~ er", for c, r # 0, > 0. Upon substitution we get crt? = er" 4 or", This pives the characteristic equation r? = 0.The character: istic roots are r = (1 5)/2, so the general solution is sy nn (188) +0 (: ‘To solve for ¢), ¢, we use the given initial values and write O= Fy = 6) +e3, 1 = F, = exl(l + 5)/21 + col — V3)/2}. Since cy ~ es, we have 2 ey(L + V5) — ex(l = 5) and ey = 1/4/5. The general solution is given by ro al3)-E3)} os ‘When dealing withthe Fibonacci numbers one often finds the assignments ¢ = (1 + V/3)/2 and B = (1 — /5)/2, where « is known as the golden ratio, As a result, we find that 1 oe = Le" 5" ee) ye - P= ae = [This representation is referred toas the Binet form for Fa, as it was first published in 1843, bby Jacques Philippe Marie Binet (1786-1856).] For n 20, let $= (1,2, 3,..-.n} (when m= 0, $= 0h, and let ay denote the number of subsets of 5 that contain no consecutive integers, Find and solve a recurrence relation foray. For 0 2 and ap = 1..a; = 2, is the recurrence relation for the problem. Now we could solve for dg, but if we notice that dy = Fay. > O, then the result of Example 10,10, vies hat ( “) a (: =] ee458 Chapter 10. Recurrence Relations EXAMPLE 2 [EXAMPLE 10.13 Suppose we have a 2 Xn chessboard, forn € Z*. The ease for n = 4is shown in part (a) of Fig, 10.5, We wish to cover such a chessboard using 2 X 1 (vertical) dominoes, which can also be used as 1X 2 (horizontal) dominoes. Such dominoes (ortiles) are shown in part (b) of Fig. 10.5 @ & © Figure 105 Forn € Z* we let by count the number of ways we can cover (or tle) a2 n chessboard using our 2 x Tand 1 X 2 dominoes, Here b; = 1,fora2 x 1 chessboard necessitates one 2. 1 (vertical) domino. A2 x 2 chessboard can be covered in two ways — using wo2 X 1 (vertical) dominoes or two 1 x 2 (horizontal) dominoes, as shown in part (c) ofthe figure. Hence b; = 2. Forn » 3, consider the last (mth) column of a2 Xn chessboard. This column ccan be covered in two ways. 1) By one 2 1 (vertical) domino: Here the remaining 2. (n ~ 1) subboard can be covered in by—1 ways fi) By the right squares of wo 1 X 2 (horizontal) dominoes placed one above the other: "Now the remaining 2 (n ~ 2) subboard can be covered in by Ways. Since these two ways have nothing in common and deal with all possibilities, we may write be b HF bea ne by We ind that by = Fy. so here is another situation where the Fibonaceé numbers arise. The result from Example 10.10 gives us by = (/V3){Cl = -V/5)/29"*" = (= V5)/20"") nel At this point we examine an interesting application where the number o = (1+ /3)/2 plays a major role. This application deals with Gabriel Lamé’s work in estimating the num- ber of divisions used in the Euclidcan algorithm to find ged(a, b), where a, be Z* with @ > b > 2. To find this estimate we need the following property of the Fibonacci numbers, which can be established by the alternative form ofthe Principle of Mathematical Induction. (A proof is requested in the Seetion Exercises.) Property: For n = 3, Fx > a2 Addressing the problem at hand —namely, estimating the number of divisions when the Euclidean algorithm is used to find ged(a, b)—we recall the following steps from Theorem 4.7,102. The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefcients 459 Letting »y = @ and ry = b, we have m=qntn, Oenen ne ant. Vener na aystre Oenen a ee ee Fat ™ en So ra, the last nonzero remainder, is ged(a, b).. From the subscripts on r we see that 7 divisions have been performed in determining re = ged(a, b). In addition, 4) > 1, for all 1 0, S0% = 1= Fe (dn * 2) (ra = WN tat day = 2-12 By fet deta thee ltt e te rps gsr Lirsb rye Feat Fea Pa bans ga tree Lore trs Fat Fat = Fou ‘Therefore, ifn divisions are performed by the Euclidean algorithm to determine ged(a. b).. witha > b 2 2,thenb > Fy4.Soby virtue ofthe property introduced earlier, we may write ba ain? [C1 + ¥5)/2)""!, Consequently, we find now that b> a?! = logis b > logig(a"") = (n— 1) logyya > since logy a = log,o{(1 + v5) /2] = 0.208988 > 0.2 = £. ‘At this point suppose that 10! < < 10°, so thatthe decimal (base 10) representation of bas k digits. Then Logg 10 > logig b > and n< Sk 1 With n, k eZ" we have n< Sk-+ 1=9-n<5k, and this last inequality now completes a proof for the following. Lamé’s Theorem: Let a, b € Z* with a > b = 2. Then the number of divisions needed, in the Enclidean algorithm, to determine ged(a, 6) is at most 5 times the number of decimal sigits in 6, Before closing this example, we lear one more fact from Lamé’s Theorem. Since b> 2, it follows that logia b 2 logy 2, 80 5 ogg B 2 5 logyq 2 = l0g9 2° = logy, 32 > 1. From above we know that n — 1 < 5 logia b, so n= 14S logy b < S logy b + 5logig b = 1 logyy > and 7 € O(log, b). (Hence, the number of divisions needed, in the Euclidean algorithm, todotermine god(a, b), fora, b € Z” with a > b > 2, is O(log jo 6) — that is, on the order ‘of the number of decimal digits in.)460 Chapter 10. Recurrence Relations EXAMPLE 10.14 {EXAMPLE 10.15 Returning to the theme ofthe section we now examine a recurrence relation ina computer science application In many programming languages one may consider those legal arithmetic expressions, without parentheses, that are made up ofthe digits O, 1,2, ...,9 and the binary operation symbols +, », /.For example, 3 + 4 and 2 +3 5 are legal arithmetic expressions; 8+ =9 is not, Here 2-43.45 = 17, Since there i a hierarchy of operations: Multiplication and division are performed before addition, Operations at the same level are performed in their onder of appearance as the expression is scanned from eft to right. For 2, let ay be the numberof these (legal) arithmetic expressions that are made up of n symbols, Then ay = 10, sinee the arithmetic expressions of one symbol are the 10 digits. Next a; ~ 100, This aecounts for the expressions 00, 01, ... 09, 10, 11, ..., 99 (here are no unnecessary leading plus signs.) When m > 3, we consider two cases in order to derive a recurence relation foray 1) IE x is an arithmetic expression of n — 1 symbols, the last symbol must be a digit. Adding one more digit to the right of x, we get 10ay_1 arithmetic expressions of 1 symbols where the last wo symbols are digits 2) Now let y be an arithmetic expression of n ~2 symbols. To obtain an arithmetic expression with symbols (that is not counted incase 1), weadjoin othe rightof y one of the 29 two-symbol expressions +1, .-. 49, +0,#1, .-. 29,40, /1,-. 4/9. From these two cases we have dy ~ 10ay-1 + 294y-2. where n > 3 and a) = 10, a3 100. Here the characteristic roots are 5£3V6 and the solution is a, = (5/(3V6)) [6 +36)" — (5 ~ 36)" forn > 1. (Verify this result) Another way to complete the solution of this problem is to use the recurrence relation ay = 10dy-1 + 2944-2, with dz = 100 and ay ~ 10, to calculate a value for ay —namely. 4) ~ (a3 ~ 104) /29 = O. The solution forthe recurrence relation tn = G/GVBMES + 3V8)" ~~ 3V8"), nO. A second method for counting palindromes arises in our next example. In Fig, 10.6 we find the palindromes of 3, 4, 5, and 6— that is, the compositions of 3 4. 5, tnd 6 that read the same left to right as right to let. (We saw this concept earlier in Example 9.13.) Consider first the palindromes of 3 and 5. To build the palindromes of 5 from those of 3 we do the following: i) Add 1 to the first and last summands in a palindrome of 3. This is how we get palindromes (1') and (2’) for 5 from the respective palindromes (1) and (2) for 3. [Note: When we have a one summand palindrome n we get the one summand palindrome m+ 2. That is how we build palindrome (1) for 5 from palindrome (1) for 3.1 ii) Append“1-+" tothe start and "+1" tothe end of each palindrome of 3. This technique ‘generates the palindromes (1") and (2") for 5 from the respective palindromes (1) and (2) for 3102 ‘The Second-Order Linear Homogeneous Recurrence Relation with Constant Coeficents 461 ( 3 ay 5 a) 4 ay 6 Q 14141/@) 24142 Q) 14241 @) 24242 ay 14341 @) 242 By 343 Maieeeeti emitter cimlsieeee nen iia tee Dele 142 an, 14441 Q’y T+1+24141 6, 1424241 @)ltlel4ei+i4 Figure 105 “The situation is similar for building the palindromes of 6 from those of 4 ‘The preceding observations lead us to the following. Forn € Z*, let pa count the number of palindromes of. Then Po=2Peze 2% pal pea? Substituting p, = or". for c,r #0, m > 1, into this recurrence relation, the resulting ehar- acteristic equationisr? — 2 ~ 0. The characteristic roots arer = 2,60 pa = cx(W2)"-+ ex(—v2)". From, T= pr er(V2) + ex(-V2) 25 pr = e(v2i + ex(-V2)? wwe find that ey Jer = (3 = xs). 80 ee et =(444 i + (5~ x45) vay. nel. me (Sta Q)OR + (G-a) oR Unfortunatly, this does not look like the result found in Example 9.13. Afterall that answer contained no radical terms, However, suppose we consider m even, say n = 2k. Then = (Jogi) ar (- gL) Pata) 27 WA it cee a (hy Lye (21) eo eon (+5a)*+G-aa) Fora oad, say n= 2k ~ 1, k © Z*, we leave it for the reader to show that p, = 2* yee ‘The preceding results can be expressed by p, = 2!"/7),n > 1, as we found in Example 9.3. ‘The recurrence relation forthe next example willbe setup in two ways. In the first part we shall see how auxiliary variables may be helpful TXAMPLE 1016] Fila recorence relation forthe umber of binary sequences of length m that have 90 consecutive 0s462 Chapter 10. Recurrence Relations 4) For n> 1, let ay be the number of such sequences of length n. Let a” count those ‘hat end in 0, and a” those that end in I. Then a = a+ a ‘We derive a ectitence relation foray, n > 1, by computing ay ~ 2and then con- sidering each sequence x of ength n ~ 1 (> 0) where x contains no consecutive 0's. Ifx ends in 1, then we can append a 0 or a 1 to it. giving us 2al"!, of the sequences counted by ay I the sequence x ends in 0, then only 1 ean be appended, resulting in {°), sequences counted by a. Since these two cases exhaust all possibilities and have nothing in common, we have a, =2-all, + 1-0, + Thesipion Theo utn beeen, Uremic twee consider any sequence y counted ind,—2 We find thatthe sequence ) is counted Tikewise if the sequence z1 is counted inal, then zis counted im dyn. Consequently, y-1 = of? and a, =, + [00, +a®] 0, + a,-1 ‘Therefore the recurrence relation for this problem is dy = dy1 + dy—2, where n = 3 sand a; = 2, a; = 3. (We leave the details of the solution for the reader.) ) Alternatively, if n = 1 and a, counts the number of binary sequences with no con- secutive 0's, then a; = 2 and ay = 3, and for n = 3 we consider the binary sequences ‘counted by dg. There are two possibilities for these sequences: (Case 1: The nth symbol is 1} Here we find that the preceding n — 1 symbols form ‘abinary sequence with no consecutive 0's, There are a1 such sequences, (Case 2: The nth symbol is 0) Here each such sequence actually ends in 10 and the first n — 2 symbols provide a binary sequence with no consecutive 0's In this case there are ay_2 such sequences. ‘Since these two cases cover all te possibilities and have no such sequence in common, we may write Oy = My Atte MEI, a as we Found in part (a). In both part (a) and part (b) we can use the recurrence relation and ay 220 back and determine a value for ay—namely, ao ~2 solve the recurrence relation 2a Then we can StF Oa me Before going any further we want to be sure that the reader understands why a general argument is needed when we develop our recurrence relations. When we are proving a theorem we do not draw any general conclusions from a few (or even, perhaps, many) particular instances. The same is true here. The following example should serve to drive this point home. We start with » identical pennies and let a, count the number of ways we ean arrange these EXAMPLE 10.17 | ennies— contiguous in each row where each penny above the bottom row touches 100 pennies in the row below it, (In these arrangements we are not concerned with whether any102 The Second-Order Linear Hornogeneous Recurrence Relation with Constant Coeffcents 463 given penny is heads up or heads down.) In Fig. 10.7 we have the possible arrangements for | 0, we obtain the characteristic equation 2r? — r? 2h +1 =0 = (2r ~ I(r = 1) + 1). The characteristic roots are 1/2, 1, and ~1, so the solution is ay, = cy(1)" + e2(-=1)" + cy(1/2)" = ey + ex(—1)" + es(1/2)". [The solutions 1, (=1", and (1/2)" ate called linearly independent because it is impossible to express464 EXAMPLE 10.19 Chapter 10 Recurrence Relations any one of them as a linear combination of the other two."] From 0 = ay, 1 = ay, and 2 = 4s, we derive ¢1 = 5/2, ¢2 = 1/6, ¢5 = ~8/3. Consequently, ay = (5/2) + (1/6)(—1"" (8/3)/2)", n= 0. For > | we want to tile a2 * m chessboard using the two types of tiles shown in part (a) of Fig. 10.8. Letting a, count the number of such tilings, we find that a) = 1. since we can tile a 2 x 1 chessboard (of one column) in only one way—using two 1 L square tls. art (b) of the figure shows us that a: ~ 5. Finally, for the 2 3 chessboard there are 11 possible tilings: () one that uses six 1 1 square tiles; ii) eight that use three 1 1 square tiles and one of the larger tiles; and (ii) two that use two of the larger tiles. When n > 4 we consider the nth column of the 2 x 1 chessboard. There are three cases to examine: 1) the nth columnis covered by two 1 X 1 square tiles — this case provides ay. tilings 2) the (nm ~ 1)st and nth columns are tiled with one 1 x 1 square tile and one larger tile —this ease accounts for 4a,» tilings; and 3) the (n — 2)nd, ( ~ L)st, and nth columns are tiled with two ofthe larger tiles —this results in 2ay_» tilings. ro le 1 f [ @ ©) | Figure 108 “These three cases cover all possibilities and no 8wo of the cases have anything in common, Oy = ays Aya 2s, ned aah ay = 11 ‘The characteristic equation x” — x — 4x ~ 2 =O can be written as, (+ Ie? = 2 — 2) = 0, so the characteristic roots are 1, 1-+ V3, and | ~ V3. Con- sequently, ay = ¢\(=1)" + ex(1 + V3)" + ex — V3)", m1. From 1 = ay =e) + ex(1 + V3) + esl — V3). 5 = ay = 01 + ex + V3)? + ex V3)? and N= ay = ey + cx(1 + V3" +6301 = ¥3)', we have e1 = Iyer = 1/3, and ce) = =1/V3. So te = Dt AVI VI IVDO = V5", net Case (8): (Complex Roots) Before getting into the case of complex rots, we recall DeMoivre’s Theorem: (cos8 +i sin oy" = cosné +i sind, — n 20. [This is pare (b) of Exercise 12 of Seetion 4.1.] ‘Aluemativoly, te solutions 1, (—1)*, and (1/2) are Fnealy independent, because I yf, ky ae eal aunbets and (1) fot H+ &y(/2P = 0 forall n= Nthen ky =k = hy =O,_ EXAMPLE 10.20 EXAMPLE 10.21 102 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefcients 465 Itz =x biy €C,z #0, weean write z= r(cos6 +i sin), wherer = (v/a) = tan 8, for.x 0. IF = 0, then for y > 0, = yi = yi sinGr/2) = y(cos(er/2) + i sin(/2)), and for y <0, = lylleos(z/2) + ¢ sin(3z/2)), 2 yi = [yl sin@x/2) Inall eases, 2* = r"(cos nf + i sin nf), for n = 0, by DeMoivre's Theorem, Determine (1 + 31)". Figure 10.9 shows a geometric way to point (1, ¥/3) in the xy-plane. Here r = v1? + (v3) resent the complex number 1 + V/Fi asthe Figure 10.9 So 1 + V3i = 2(cos(a/3) + é sin(r/3}), and (14 V3.1)! = 2!(eos(102/3) +7 sin(1Os /3)) = 2!(cos(4r/3) +i sin(4/3)) 210(=1/2) — (3/291) = (-BU + VFA). ‘We'll use such results in the following examples, Solve the recurrence relation ay = 2(a ~ dy-2), where n > 2 and ay = 1, a) = Letting a, = er", for e.r #0, we obtain the characteristic equation r? ~ 2r + 0, whose roots are 17. Consequently, the general solution has the form e(I +A) + ca(1 = 1)*, where ¢; and cp presently denote arbitrary complex constants. [As in case (A), there are two independent solutions: (1 +i)" and (I~ i)".] 1 +i = V2(cos(xr/4) +i sin(or/4)) and 1-5 = VF (eos =n/4) +4 snl —70/4)) = VHeostr/4) ~ i sintr/4),966 Chapter 10 Recurrence Relations ‘This yields ay = e((L +i)" teal =" = el V2tcos(er/4) + i sin(x/4))I" + cal V2(cos(—n/4) + i sin(—n/4))]" V2)" (east /4) + 7 sin /4)) + €2(V2)"(cos(—ne /4) + 1 sin(—nt/4)) = eB" (costes /4) + # sin /4)) + e2(/2)" Coste /4) ~ i sini /4)) = (V2)"Uki cost /4) + ke sintnx/4)], where ky = cy + ¢3 and k; = (ey ~ ey). 1 = ay = [hy 608 0 + ba sin O1 = ky 2 VAIL - cost /4) + ky sin(wr/4)}, or 2 = 1+ a, and ky 7 ‘The solution for the given initial conditions is then given by ay = (V2)"[cos(n/4) + sin(n/4)]. nn =O. [Note: This solution contains no complex numbers. A small point may bother the reader here, How did we start with e1, ¢2 complex and end up with ky = er +6, and ky = (e, = c2)i real? This happens if), c2 are complex conjugates.] Let us now examine an application from linear algebra. TRAMPLE 10.22] Fore RY, consider the n x n determinant’ D, given by bb 000 00000 bb boo ooo000 0b bb 0 00000 0 0 6 bb 00000 lo o000 bbboOoO loo 000 0b b bo loo 000 O0bbS oo000 00068 Find the value of Dy as a function of Let dp, m > 1, denote the value of the n Xn determinant Dy. Then lb bo bbb lob » a=[l=6 and az={P Pl =0 Gand as “The expansion of determinants i discussed in Appendix 2.EXAMPLE 10.23 102 The Second-Order Linear Homogeneous Recurrence Relation wth Constant Coefficients 467 Expanding D, by its first row, we have Dy = bboO 0000 b boo rn) bbbO 0000 an) o000 Obb>b 0000 Ob bd oo00 b -b joooo bb bo 0000 bb bo 0000 Obb>b 0000 Ob bb loo00 0066 lo 00 oobb iss, 1) ‘When we expand the second determinant by its first column, we find that D, = bD,-1 ~ (®)(6)D,_2 = bD,1 ~ 6° Dy-a. This translates into the relation ay = bay — baa, for n= 3,a) =b,a2 I weletay = or" fore. # Oand n> |, the characteristic equation produces the roots 0/2) 215/21 Hence fag = e(D((1/2) + V3/20P + cal((1/2) — VIP = brey(cos(a/3) +6 sin(/3))" + = BM ky cost /3) +f sin(nz/3)] lbs cos(er/3) + kz sin(x/3)], $01 = x(1/2) + k2/3/2), or ky + V3 = ky cos(2zr/3) + ke sin(2x/3)], 50.0 = (i )(—1/2) + ka(V/3/2), oF hy = V3k; ws(or/3) ~ i sin(e/3))") Hence ki = 1, kz = 1/3 and the value of Dy is b*foos(nm/3) + (1/V%) sing /3)] Case (): (Repeated Real Roots) Solve the recurrence relation dgs2 = Adn1 ~ Ady, where > O and ay = Ieay = 3, AS in the other two cases, we let dy = cr", where c, r #0 and n > 0. Then the charac- teristic equation sr? — 4r + 4 = O and the characteristic roots are both 7 = 2. (Sor = 2is called “a root of multiplicity 2.”) Unfortunately, we now lack two independent solutions: 2" and 2" are definitely multiples of each other, We need one more independent solution, Let us try g()2" where g(n) is not a constant. Substituting ths into the given relation yields = 4g@n + 12"! — dgon2" gin +292" g(r +2) = 2g(n + 1) ~ ger. 0 One finds that g(x) =n satisfies Eq, (1).' So n2" is a second independent solution. (It is independent because itis impossible to have n2" = k2* for all n > O if k isa constant.) Actually the genta sobion gm) ~ a +, frapbitraty constants, witha #0. Here weehosear = and b~ Ow make s(n) simple a posible468 Chapter 10. Recurrence Relations ‘The general solution is ofthe form ay = e4( + (1/2)n(2") = 2" + ) + ean (2"). With ag = 1a) = 3 we find nQtyn > 0, In general, if Cody + C1dq-1 + Cady-2++ + Crqe = 0, with Co (#0), C1, Co, + Cy (#0) real constants, and r a characteristic root of multiplicity m, where 2. 2. Since py = 0 and Py = 1, ifthe first case (of a new outbreak) is recorded on Monday, March 3, 2003, when did the probability for the occurrence of a new ease de time? ase to less than 0.01 forthe fist With p, ~ cr" fore, r # 0, the characteristic equation for the recurrence relation is? ~ r+ayy (r ~ (1/2))*. The ger n> 0.For po = 0, p, = I, we get c; = 0, solution has the form py = (ci + e3n)(1/2". 2 = 2,50 py = 22" 20. The first integer n for which py < 0,01 is 12. Hence. it was not until the week of May 19, 2003, that the probability of another new case occurring was less than 0.01 Era 1. Solve the following recurrence lations. (No final answer should involve complex number.) 8) ay = Say + 6 dy 35 = Naya + 5a, n>, a=, a =3 0, m=O, ay =0, 120, a =O, « ) ey ~ Bay) + 94-3 = 0. = 2, ay 2 ©) dy + 2g +220, HEX y=, ay = 3 2. a) Verify the final solutions in Examples 10.14 and 10.23, D) Solve the recurrence relation in Example 10.16 3. Ih ay =0, 37 satisfy the recur. rence relation a,,2-+ ays1 + et, = 0, where n = 0 and b, se constants, determine be and salve for a, 4. Find and solve a recurrence elation forthe number of ways to park motorcycles and compact cars in a ow of n spaces if each eycle requires one space and each compact needs tWo.(AlL cycles are identical in appearance, ay are the ears, and we Want to use up ll the n spaces.) 5, Answer the question posed in Exeweise 4 iF (a) the motor cycles come in two distinct models; (b) the compact ears come in thee different colors; and (c) the motoreycles come in two distinct models and the co act cars come in three different alors, 6. Answer the questions posed in Exercise $ if empty spaces av allowed, 7. In Exercise 12 of Section 4.2 we leasned that Fy + Fi Ft = Dlg A= Fear b. This is one of many such properties of the Fibonacci numbers thac were discovered by she French mathematician Frangois Lucas (1842-1891)-Al though we established the result by the Principle of Mathemat- ical Induction, we see that itis easy to develop this formula by adding the system of n+ 1 equations ReB-K R- Fata Fe102. The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefcens Develop formulas for each of the following sums, and then check the general result by the Principle of Mathematical a ‘setion a Rts DHT Rt RS 8. a) Prove thar + Fax ts heren eZ" + Foy where n eZ 4y5 Lim An, (This limit has come o be known as the golden rato and is often designated by a, as we mentioned in Example 10,10.) ) Consider a regular pentagon ABCDE inscribed ina cir cle, a8 shown in Fig. 10.10, 1) Use the law of sines and the double angle formula for the sine to show that AC/AN = 2c0s 36" )Ascos 18° = sin 72" = 4 sin 18° cos 18°(1 — 2 sin? 18°) (Why?), show that sin 18° is root of the polynomial equa tion &c! = 4x + 1=0, and deduce that sin 1 = (5 iA ©) Veify bat AC/AX = (1+ YS)? 8 A © é 2 Figure 1010 9. For m0, let ay count the number of ways a sequence of Fs and 2's will Sum to n. For example, « (1) 4,145) 1,2:and 2, 1 sumo 3. Findand solve a recur rence elation fo 10, For = |0, 1),let A CE", where A = (00, 1)-Forn = 1. let ay count the numberof strings in A” of length n. Find and solve a recurrence relation fora. (The reader may wish o refer to Exercise 25 for Section 6.1.) 4) Form > 1, let, count the numberof binary strings of length, where there are n0 consoeutive I's, Find and solve a rocortenee relation foray b) Form > 1, let, count the numberof binary strings of length m, where theve are no consecutive 1's and the fist and last bit ofthe string are not both 1. Find and solve @ recurrence relation for by 12, Suppose that poker chips come in four colors —red, white, seen, and blue. Find and solve a recurrence relation for the numberof ways to stack n ofthese pokerchips so tht there ae to consecutive ble chip 13, An alphabet consists ofthe four numeric characters 1 2, 5,4, andthe sven alpha characters, 8,6 df Findand oie arcumence eatin for the nmberof words of lengthm Gn 2"), where here are no eonscetive (etal inti) alphabetic characters. 14, An siphabot E consists of seven mumerie characters and Ar alphabctie characters, For n= 0, courts the number of sings (in E*) of length tht conan no comes ie calor sine) alphabetic charters sy = Toys + 63m t= O,shat isthe vale of F? 1S Solve the recurrence relation ds a2 16, Form 1, ta, be the numberof ways to write mas ance ered sum of postive integers, where each summand st east 2.(Forevanpie, as = 3 beetne here we ay represent 3 BY. by 243. and by 342) Find and slve a reutence elation fora, 11, a) For fixed nonnegative integer, how many composi jos of + Shave no fsa sornmand? 'b) For the compositions in part (a), how many start with (25 (i) 3 Gi, whee 22k a and (cer 22, ) Form 7°, let a, count the mmber of palindromes of 2n.Them dy = 2am Iya) 2 Sole thi reorder recumence elation frag b) Form 2°, le hy count the mamber of palindromes ot dn — 1. Set up and seve a fistonerrecrence relation for by. (You may wantto compare your soluionsher with those givem in Examples 913 and 1018) 23, Consider emary strings — tat, strngs where, 1.2 are the only symbols ose. Foe >I let. et the namber of temary sings of length n wre thee arena conscesive I's and no consecutive 2s Find and solve a recente lation foran invites 2 O,ayATO Chapter 10 Recurrence Relations 24. For m2 1, let dy count the number of ways to tle a ‘taessboardl using horizontal (1 % 2) dominoes [which cx also be used as vertical (2 1) dominoes} and square (2 X 2) tes Find and solve a recurrence relation ford 28, Tn how many ways can one tile a2 % 10 chesshoard using ‘dominoes and sjuare tiles (asin Exercise 24) ifthe dominoes ‘come in four colors and the square tiles come in ive colors? 26, Let E = {0, Tand A = 40,01, 1). E*. Porn > Iletay Count the numberof strings in A” of length n, Find and solve a recurrence elation foray 27. LetD = (0, t}and A = 40, 01,011, 11) © E*.Forn = 1, Jet ay count the numberof strings ia A* of length n. Find and solve a recurrence relation foray 28. Let E = (0, 1) and A= 0, 01,011, 0111, LN} CE" Forn > |, eta, count the numberof stings in A* of length Find and solve a recurence relation for cy 29. A particle moves horizontally to the right. Form & Z*, the slstance the particle uavels in the (n+ 1)st second is equal to ‘wie the distance it ravels during the nth second. Ixy. > 0, ‘denotes the postion of the particle a the star of the (2 + 1st second, find and solvea recurrence relation for xy, Where x ands, = 5; 103 The Nonhomogeneous Recurrence Relation 30, For n= 1, fet Dy be the following m X n determinant, 21000 a) 12100 a) o1210 0 0 0 00000 alasablicto 00000 Ong bere ul 00000 onosieti2| Find and solve a recurrence relation forthe value of Dy Sai, +408 = 0, BA Solve the recurence relation @2 where x= Oand.ay = 4,4) = 13. 32, Determine the constants band cite, =e) + ex(7).n>0, 's the general solution of the rolation dgg2 + Bases + 64 0,n20. 33, Prove that any two consecutive Fibonaect numbers are el atively rime, 4M. Write 4 computer program (or develop an algorithm) to ‘determine whether a given nonnegative integer isa Fibonacci number, ‘We now tum to the recurrence relations iy + Cy, ag + Chg + Crt. nel, a Fin), Fa), 22, a where Cj and C; are constants, Cy # 0 in Eq. (1). C; #0, and f() is not identical 0. Although there is no general method for solving all nonomogeneous relations, fr erin functions f(n) we shall find a successful technique. ‘We start with the special ease for Eq, (1), when C; = =I, For the nonhomogeneous relation dy ~ ayy = fn), we have a; = ay + fl) ay = a + (2) = ag + £1) + $2) 3 = ay + $3) = ay + FI) + $2) + G) + DFO. + fim) = ay + FF + Fo We can solve this type of relation in terms of, if we ean find a suitable summation formula for 52", fi).["exampte 1025 EXAMPLE 10.26 | EXAMPLE 10.27 103. The Nonhomogeneous Recurrence Relation an Solve the recurrence relation ay ~ ay Here f(n) = 3n?, so the unique solution is os at Es DD Sn?, where > 1 and ay = 7. 1 Simin + Qn + 1). When a formula for the summation is not known, the following procedure will handle Eq, (1) for certain functions f(n), regardless of the value of C\ (0). It also works for the second-order nonhomogeneous relation in Eq. (2)—again, for certain functions. (n) Known as the method of undetermined coefficients, itrelies on the associated homogeneous ‘elation obtained when f (n) is replaced by 0. For either of Eg. (1) or Eq. (2), we let af denote the general solution of the associated homogeneous relation, and we let 2 be a solution of the given nonhomogeneous relation. The term a{?” is called a particular solution. Then a, ~ a!" + al” isthe general solution ofthe given relation. To determine a? we use the form of f(n) to suggest a form fora” Solve the recurrence relation dy ~ 3ay-1 = 5(7"), where n > 1 and ay ‘The solution of the associated homogeneous relation isa"? = e(3").Since f(n) = 5(7"), 4 particular solution a” of the form A(7"). As ay” is to be a solution of the given nonhomogeneous relation, we place ai!” = A(7") into the given relation and find that A(M") — 3A7"~!) = 5(9"),m > L. Dividing by 7*~!, we find that 7A ~ 34 = 5(7), so A= 35/4, and al?” = (35/4)7" = (5/4)7"7), n > 0, The general solution is ay (5/471. With2 = ay = ¢ + (5/4)(9),itfollows thate = ~27/4and ay = (5) C/G), nO. Solve the recurrence relation ia ~ 3ay-1 = 5(3"), where n > 1 and a As in Example 10.26, a\®) = e(3"), but here a and f(n) are not linearly independent. Asa result we consider a particular solution af” ofthe form Bn(3*). (What happens if we substitute af?” = (3) into the given relation?) Substituting ef?” = Bn3" in the given relation yields Bra") — 53"), or Bn~ Bal) Bin — 1)3""") so B=S. Hence ay = a) + af? = (e+ 5n)3%.n (2+ 5n)(3"),n 20. = 0. With ay = 2, the unique solution is ay = From the two preceding examples we generalize as follows. Consider the nonhomogeneous first-order relation y+ Cydy1 =k, where kis @ constant and n € Z*.Ifr* isnot a solution ofthe associated homogeneous relation a, + Cidp-a = 0, then af?’ = Ar", where A is a constant, When ris a solution of the associated homo- _gencous relation, then ay” = Brr*, for B a constant.972 Chapter 10. Recurrence Relations EXAMPLE 10.28 Now consider the case of the nonhomogeneous second-order relation Oy + Cydyni + Cada = kr”, where & is a constant. Here we find that a) ai” = Ar’ for A aconstant, ifr" is nota solution of the associated homogeneous relation, b) of? = Bar’, where Bisa constant if af = our" + cart where ry 7 ri and ©) al? = Cnr for C a constant, when af? = (cy + ean)r" The Towers of Hanoi. Consider n circular disks (having different diameters) with holes in their centers, These disks can be stacked on any of the pegs shown in Fig. 10.11. In the figure, n= 5 and the disks are stacked on peg 1 with no disk resting upon a smaller one. The objective isto transfer the disks one at a time so that we end up with the original stack on peg 3. Each of pegs 1, 2, and 3 may be used as a temporary location for any disK(s), but at no time are we allowed to have a larger disk on top ofa smaller one on any peg. What is the minimum number of moves needed to do this for m disks? Figure 10.11 For n = 0, let dy count the minimus number of moves it takes to transfer m disks from peg | to peg 3 in the manner described. Then, form + I disks we can do the following: 48) Transfer the top n disks from peg 1 to peg 2 according to the directions that are given. This takes at least a, moves, bb) Transfer the largest disk from peg I to peg 3. This takes one move, ©) Finally, eransfer the n disks on peg 2 onto the largest disk, now on peg 3—once again following the specified directions. This also requires a least a, moves. Consequently, at this point we know that dy. iS no more than 2a, + 1 —that is, inj < 2ae + 1. But could there be a method where we actually have ag, < 2ay + 1? Alas, no! For at some point the largest disk (the one at the bottom of the original stack —on peg 1) ‘must be moved to peg 3. This move requires that peg 3 has no disks on it. So this largest disk may only be moved to peg 3 after the n smaller disks have moved to peg 2 [where they are stacked in increasing size from the smallest (on the (op) tothe Targest (on the bottom)] Getting these n smaller disks moved, accordingly, requires at least aq moves. The largestEXAMPLE 10.29 EXAMPLE 10.30 103 The Nonhomogeneous Recurrence Relaion 473 disk must be moved atleast once to get ito pez 3. Then, vo get the n smaller disks on top of the largest disk (all on peg 3), according to the requirements, requires atleast dy more steps. So duyi 2 ae + hy = 2an + With 24, +1 < dye ¢ 20m + 1, we now obtain the relation gy = 2a, + 1, where r= O and ay =0. For dg ~ 2ap = 1, we know that a = e(2"). Since f(n) = 1 Of ayy} ~ 2dy =, we set af” A(1)* = A and find from the given relation that A — 2A4'1,s0 A= =1 and ay = c(2") ~ 1, From ay =0-= ¢~ 1 itthen follows that © = 1, $0 de = 2" ~ 1.n 20. (Q)" isnota solution ‘The next example arises from the mathematics of finance Pauline takes out a loan of $ dollars that is to be paid back in T periods of time. If isthe rate per period for the Loan, what (constant) payment P must she make at the end of each period? We let ap denote the amount still owed on the loan atthe end of the nth period (Following. the nth payment). Then atthe end of the (n + I)st period, the amount Pauline still owes on her loan is ay (the amount she owed at the end of the nth period) + ray (the interest that aacerued during the (n + I)st period) ~ P (the payment she made atthe end of the (r+ I)st period). This gives us the recurrence relation ast =p tray PON ST a= 5, ar=0. For this eeation a = e(1 +7)", while af” = A since no constant is a solution of the associated homogeneous relation. With al?” = A we find A— (1+) = —P, so A P/r. From ay = S, we obtain ay = (S—(P/rl +r" + (P/r}. 050 = Since 0 = ar = (S~ (P/n)\L +r)? + (Pin, follows that Pins (PiN- Hd +n! and P= (Sntl- Gere We now consider a problem in the analysis of algorithms Forn > I, et $ bea set containing 2" real numbers The following procedure is used to determine the maximum and minimum elements of ' We wish to determine the number of comparisons made betwcen pais of clements in $ during the execution ofthis procedure. Ifa, denotes the number of needed comparisons, thena, = 1.Whenn = 2,| S| = 2° = 4, 80 $= [x1. x2. y4y Ya} = Sy U Sp where S) = (x1, x3}, Sp = {y1. ya}. Since ay = 1, ittakes one comparison to determine the maximum and minimum elements in each of Si, 5 Comparing the minimum elements of $1 and Sy and then their maximom elements, we tearm the maximum and minimum cloments in $ and find that ay = 4 = 2ay +2. In genera, if |S] = 2"*!, we write § = $ US; where |S;| = |Sz| = 2". To determine the maximum and minimum elements in each of §, and S> requires a, comparisons, Comparing the ‘maximum (minimum) elements of Sy and Sz requires one more comparison; consequent, digs} = 2ay +2. 1 Herea!® = ¢(2")anda,?” = A.aconstant Substituting A=2A-42,0rA=—2. Soa, = e2" ~2,and with a; = 1 Therefore a, = (3/2)(2") — 2. into the relation, we find that 2c — 2, we obtain ¢ = 3/2.474 Chapter 10. Recurrence Relations A note of caution! The existence of this procedure, which requires (3/2)(2") — 2 com parisons, does nor exclude the possibility that we could achieve the same results via another remarkably clever method that requites fewer comparisons. ‘An example on counting certain strings of length 10, for the quaternary alphabet © (0, 1, 2,3}, provides a slight twist to what we've been doing so far For the alphabet £ = (0, 1, 2, 3}, there are 4" = 1,048,576 strings of length 10 (in Z"°, [xampus 10st | 357 Now we want to ksow how many of hese mor than Lmlion tangs contin at even numberof 1 ane ae onsier the th symbol of one of thet ang feng (wher thr isan even uber ory. Two cases ae ee aa me sytials, Thre re 4" sng length I and ve wart o avd ene that have an even number of 1's — there are 4”~! — a,_; such strings. Consequently, this second case gives us 4"~! — a, of the strings counted by dy. ‘These two cases are exhaustive and mutually disjoint, so we may write fig = Bayan + (BY = gat) = aga tA =. Here a = 3 (for the strings 0, 2, and 3), We find that of! = e(2") and a”? = Ata? Upon substituting ai” into the above relation we have A(4"-") = 2A(#"-2) + 4°-!, so 4A = 2A +4 and A = 2. Hence, ay = c(2") + 24-4), n> 2. From 3 = ay = 2e+2it follows that ¢ = 1/2, s0dy = 2"-! 4 2(4"=!),n > 1 ‘When = 10, we learn that of the 4" = 1,048,576 strings in 5", there are 2(4°) = $24,800 that contain an even number of 1’s, ‘Before continuing we realize thatthe answer here for a can be checked by using the exponential generating function f(x) = So) developed in Section 9.4 we have ant het ao From te chu Fe) OES Of Here ay = the coeftciem of 3 in f(x) = (5) 4° + (J) 2° = 2-1 +241), as above,103 The Nonhomogeneous Recurrence Retaion 475 ‘In 1904, the Swedish mathematician Helge von Koch (1870-1924) created the intriguing curve now known as the Koch “snow#lake” curve. The construction ofthis eurve starts with an equilateral triangle, as shown in part (a) of Fig. 10.12, where the triangle has side 1, perimeter 3, and area ¥3/4. (Recall that an equilateral triangle of side s has perimeter 39 and area s?/3/4.) The triangle is then transformed into the Star of David in Fig. 10.12(b) by removing the middle one-third of each side (of the original equilateral triangle) and attaching a new equilateral triangle whose side has length 1/3. So as we go from part (a) to part (b) in the figure, each side of length 1 is transformed into 4 sides of length 1/3, and we get a 12-sided polygon of area (3/4) + (3)(V3/4)(1/3' = ¥3/3. Contin the process, we transform the figure of part (b) into that of part (c) by removing the middie one-third of each of the 12 sides in the Star of David and attaching an equiltcra ti- angle of side 1/9 (= (1/3)*). Now we have [in Fig. 10.12(c)] a4?(3)-sided polygon whose (3/3) + ANBV3/4)LL/3°P = 103/27. @ Cy co Figure 10.12 For n = 0, eta, denote the area of the polygon P. obtained from the original equilateral triangle after we apply » transformations ofthe type described above [the fist from Ps in Fig. 10.12(a) to Py in Fig. 10.12(b) and the second from P; in Fig. 10.12(b) to Ps in Fig. 10,12(0)]. As we go from P, (with 4"(3) sides) to Pyy (with 4"*'(3) sides), we find that in + AAV B/ANLIS ay + UAV)" because in transforming P, into P,. we remove the middle one-third of each of the (3) sides of P, and attach an equilateral triangle of side (1/3*!"), ‘The homogencous part of the solution for ths first-order nonhomogencous recurrence relation is al! = A(1)" = A. Since (4/9)* is not a solution of the associated homoge- neous relation, the particular solution is given by ai” = B(4/9)", where B is @ constant. Substituting this into the recurrence relation a1 = ay + (1/(4V3))(4/9)", we find that B= (-9/5)(1/(4V3)). Consequently, a, = A+ (-9/SV/AVIICA/IN" = A = ASV3N/N", 20. Since 3/4 = ay = A ~ (1/(5V3))(4/9)-", it follows that A = 6/(5V3) and aig = (6/3) — AI SVINA/N™ | = AUSVINIG = 4/9)", 20.976 ——Ghapter 10. Recurrence Relations EXAMPLE 10.33, EXAMPLE 10.34 [Asn grows larger, we find that (4/9)*~ tends to 0 anda, approaches 6/(5.V3). Weean also obtain this value by continuing the calculations we had before we introduced our recurrence relation, thus noting that this limiting area is also given by (3/4) + W3/ABDASE + (W3/MABIL/SY + (3/4 VOI = (WF/4) + (3A) D438? = (3/4) + C/AVD) Gy" V3/4) + (LIV SNNLL/ = (4/9))] = (3/4) + L/AV3O/5) = 6/53) by using the result for the sum of a geometric series from part (b) of Example 9.5. For n= 1, let Xq = [1, 2,3,..., 7]: ®(%q) denotes the power set of Xy- We want to determine ay, the number of edges in the Hasse diagram forthe partial order ((X.). S) Here a; ~ land az = 4, and from Fig. 10.13 it follows that +2) Figure 1015 This is because the Hasse diagram for (P(X), S) contains the a> edges in the Hasse di- aagram for (P(X). S) as well as the a> edges in the Hasse diagram for the partial order (((3}. U3), (2, 3) 1. 2, 3H), <). (Note the identical structure shared by the partial or ders (P((1, 2)), S) and ({(3}, (1, 3), (2. 3}, (1, 2.31], Sl In addition, there are 2? other (dashed) edges —one foreach subset of (1. 2}. Now forn > 1, consider the Hasse diagrams forthe partial orders (9(Xq), S)and ((T U fx + I}|T € 9°(Xq)). ©). Foreach $e P(Xe) draw an edge from $ in ((Xq), €) to SUin + 1} in((T U fn + IT € PX). S). The result isthe Hasse diagram for (P(X 1), S). From the construction we se that ays = May $2", a= The solution to this recurrence relation, with th ne. fen condition ay = 1, i8 ay = n2"!, Each of our next two examples deals with a second-order relation Solve the recurrence relation ya2—Adent + 3p = ~200, n=O, a = 3000, a, = 3300,103 The Nonhomogeneous Recurrence Relation ATT Here ait? = 6,(3") + ex(1") = €4(3") +e. Since (a) = ~200 = ~200(1) isa solution of the associated homogeneous relation, here al?” = An for some constant A. This leads uso Alm +2)~4A(n 41) 43An = -200, so. = 2A=-200, A= 100. Hence ay = ¢)(3") +62 + 100n, With ay = 3000 and a; = 3300, we have ay = 1003") + 2900 + 100n, n= 0. Before proceeding any further, a point needs to be made about the role of technology in solving recurrence relations. When a computer algebra system is available, we are spared much of the drudgery of computation, Consequently, all our effort can be directed to analyz- ing the situation at hand and setting up the recurrence relation with its initial condition(s), (Once this is done our job is just about finished. A Tine or two of code will often do the tick! For example, the Maple code in Fig, 10.14 shows how one ean readily solve the recurrence relations of Examples 10.33 and 10.34. [> simplity(% 7 > rsolve({a(n42)=4*a (ne1) +34a(n) 100 3° + 2900 + 100 n 1000, a2: 300), a(n)? | Figure 1038 In part (a) of Fig. 10.15 we have an iterative algorithm (written as a pseudocode procedure) ‘or computing the nth Fibonacei number, for n > 0, Here the input is a nonnegative integer nv and the output is the Fibonacci number F,. The variables i, fb, fast, next 10_last, and. temp ate integer variables. In this algorithm we calculate F, (inthis case for n > 0) by first assigning or computing all of the previous values Fo, Fy, 2, -.., Fy-1- Here the number of additions needed to determine F, is 0 forn = 0, 1 and n ~ | (within the for loop) for art (b) of Fig. 10.15 provides a pseudocode procedure to implement a recursive algo: rithm for calculating F form € N. Here the variable fib is likewise an integer variable. For this procedure we wish to determine a, the number of additions performed in computing Fy, > O. We find that dg = 0, ay ~ O, and from the shaded line inthe procedure — namely fib ;= FibMumain - 2) + Fibwuma (a - 2: . we obtain the nonhomogeneous recurrence relation Gy = dy bia t ln 22, where the summand of 1 is due to the addition in Eq. (*,478 (Chapter 10 Recurtence Relations procedure Fibsumi (n: nonnegative integer} begin Lfn~ 0 then fib :-0 else ifn=1 then ibiel temp := last Jast + next_to last rext_to last := temp end fib := last end, ond fa) procedure Fib\un2 (n+ nonnegative integer} begin i£n-0 then Eb i= 0 elee if n-1 then fib ied else fib re FibNum2(n- 1) + FibNun?(n - 2) end tb) Figure 1015 Here we find that al!” = ¢,(435)" + c2(15%S)" and that ay?” = A, a constant. Upon substituting ay” into the nonhomogeneous recurrence relation we find that A HAG $0.4 = Vand ag = c1(438)" + e2( 538)" — Since ay = 0 and a: = Ot follows that eet ad a(S) 40 (5S (V5 ~ 1/25). There- From these equations we learn that c1 = (1 + V5)/@QV3). fore, an = (1t¥3) (14 98\"_ “Vw V2 145)" sacs105 The Nonhorogeneous Recurrence Retain 479 As m_gets larger [(1 ~ ¥5)/2]"*' approaches 0 since |(1~ ¥3)/2} <1, and ay = VSIA + V5)/20*1 = (C+ ¥S2VSNG + V9)". ‘Consequently, we can see that, asthe value of increases the frst procedure requires {ar less computation than the second one does. ‘We now summarize and extend the solution techniques already discussed in Examples 10.26 through 10.35 Given a linear nonhomogeneous recurrence relation (with constant coefficients) ofthe form Coty + Cit + Cuty2 +++ Cudy-« = Fn). where Co # OandCe £ 0.letal"? denote the homogeneous part of the solution a, 1) Ff isa constant multiple of one ofthe forms in the fist column of Table 1022 and is not a solution of the associated homogeneous relation, then aj?” has the form shown in the second column of Table 10.2, (Here A.B, Age Ate Asse Arcs A, are constants determined by substiting into the given relation fr. and are aso constants) ‘Table 10.2 c.aconstant | A,aconstant n Ain+ Ay » Aun? + Ain + Ag nee ce Ain! Ain pe Ayn t Ay mreR art sin dn Asin 6n + B cos On cosa Asin 6n + B cos 6 nie PMAyn ob Ap antl eee ch Ayn + AQ) sin On AP" sin @n + Br* cos én cos én Ar" sin Bre + Br* cos @n 2) When_f(n) comprises a sum of constant multiples of terms such as those in the fist column of the table for item (1), and none of these terms is a solution of the associated homogeneous elation, then” is made upofthesum ofthe coresponding terms in the column headed by ay”, For example, if f(r) = n? +3 sin 2n and no summand of f(r) i a solution ofthe associated homogeneous relation, then ai?” = (Ayn? + Ayn + Ag) + (Asin 2n + B cos 2n, 3) Things get trickier if a summand fn) of f(n) isa solution of the associated homo sene0us relation. This happens, for example, when f (n) contains summands such as cr" oF (61 + can)?" and r isa characteristic root. i fin) causes this problem, we ‘multiply the trial solution (a?) corresponding o fy(n) by the smallest power of», say ', for which nosummand ofn () isa solution ofthe associated homogeneous relation, Then n* (af) isthe corresponding par of af”, In order to check some of our preceding remarks on particular solutions for nonhomo- geneous recurrence relations, the next application provides us with a situation that can be solved in more than one way.480 Chapter 10 Recurrence Relations EXAMPLE 10.36 EXAMPLE 10.37 For > 2, suppose that there are n people at «party and that each ofthese people shakes hans (exactly one time) with all ofthe other people there (and no one shakes hands with himself orhersei. If ay counts the total numberof handshakes, then anit Hatem, mz2 0 wad, @ because when the (n + 1st person arrives, he or she will shake hands with the » other people who have already arrived. ‘According tothe results in Table 10.2, we might think that the rial (particular) solution for Eq, (3) is Ain-+ Ap, for constants Ag and A). But here the associated homogeneous relation is dest = de OF dey ~ dq = 0, for which ai® = e(1") =e, where e denores an arbitrary constant, Therefore, the summand Ag (in Ayn + Ay) is solution ofthe associated homogeneous relation. Consequently, the third remark (given with Table 10.2) tells us that ‘we must multiply Aj71 + An by the smallest power of n for which we no longer have any constant summand, This is accomplished by multiplying Ain + Ay by n', and so we find here that ai? = Ayn? + Aon. ‘When we substitute this result into Eg. (3) we have Ay(n + 1)? + Ao(n +1) = Ayn? + Agn +n, for Ain? + (2Ay + Aa) + (Ay + Ag) = Aan? + (Ag + Dn. By comparing the coefficients on like powers of n we find that (Py AL= Ay: (my 2A, + Ap = Ay + Teand Wx, Art Ay =O. Consequently, Ay = 1/2 and Ag = 1/2, so ay” = (1/2)n? + (=1/2)m and ay = a! + all! = c+ (1/2)(n)(n = 1), Since az = 1, it follows from 1 = + (1/2)(2)(1) that and dy = (1/2)on}(n — 1), form = ‘We can also obtain this result by considering the n people inthe room and realizing that each possible handshake corresponds with a selection of size 2 from this set of size n — and there ane (3) = (nt)/A2%Gn — 23!) = 1/2)(n)(n — 1) such selections. {Or we can consider the m peopie as vertices of an unirected graph (with no loops) where an edge corresponds ‘with a handshake. Our answer is then the number of edges in the complete graph Ky and there are (3) = (1/2)(n)(n — 1) such edges.) (Our last example further demonstrates how we may use the results in Table 10.2. a) Consider the nonhomogeneous recurrence relation aq42 — 10aq41 + 2lay im), 20, Here the homogeneous part of the solution is af? = 613") Fex(7"), for arbitrary constants ec. In Table 10.3 we list the form forthe particular solution for certain choices of f(r). Here the values of the 11 constants A,, for 0 <7 < 10, are determined by substituting ai!” into the given nonhomogeneous recurrence relation.103 The Nonhomogeneous Recurrence Relation 481 Table 103 Ay | Sn? =2 Ay?+ Amn +Ay | 7a) AMC") B10"), 23.7 | Ale?) 6") Aes 20) = 89") 43") +30) Ann3* + Ag(9") Ayn 3* + AygnT™ 'b) The homogeneous component of the solution for Gy + May + Magn = Fm) af) = e\(—2)" + exm(—2)", where ¢), c> denote arbitrary constants. Consequently, D if fom) = 5-29. thenal” 2) if fn) = Tn(—2)", then ay” = nt 3) if f(m) = —11n?(—-2)", then ay” = n?(—-2)"( Brn? + Bin + Bo). (Here, the constants A, Ang Ais Bs By and are deterined By subsiaing al? into the given nonhomogeneous recurtence relation ) An'(-2)" "(Ain + Ag); and 8) ya Bangs $2au= 3, mE0, a =O. ai =1 1, Solve cach of the following recurrence relations DB) cosa + dps 4+ 40q Te =O, y= Na A) gst ay = 2N+3, =O, ay =1 6. Solve the recurrence relation ae.2 — Stas +96, D) aye dy = 3a? =n m0, ay =F 32°) + 702"), where a 2 Oand ag ee gas 7. Find the general solution forthe recurrence relation 465 = Baya + ges = dy = 34 $0, >0. ast ~2ate= 2, 020, ay 8 Determine the number of naligit quaternary (0, 1.2.3) sequences in which there is never & 3 anywhere to the Fight of 0. 9. Meredith borrows $2500, at 12% compounded morshly, «9 2, Usearecurrene ation to derive the formula for Ei? 3. a) Let Hines be drawn in the plane such that each line inmersects every other line but no three lines are ever co- incident Forn 2 0, let a, count the number of regions into plane is separated by the lines. Find and solve recurrence relation For dy b) For the situation in part (a), let, count the number o infinite regions that resulk, Find and solve a recureence relation for, 4 On the first day of a new year, Joseph deposits $1000 in ‘an account that pays 6% interest compounded monthly. A the toginning of each month he adds $200 to his account. IF he continues t0 do this forthe next four years (so that he makes 47 aitional deposits of $200), how much will bis account be wort exactly four year after he opened it? buy’ computer. If the loan isto be paid back over two years, what is his monthly payment? 10, The general solution of the recurrence relation ay.2 + basa + boty bye + bn 2 0, with , constant for If A ive2" +053" +0 —7.Findb, foreach Lf <4 1, Solve the following recurrence relations a) a2, — Sad, +602 =I, m0, ay =a = by af — 2a =O, m= 1 ay=2 (Let by = log, ays nz0) 12, Let E = (0,1, 2,3}. Form 1let a, count dhe number of strings in ©* containing an odd number of 1's Find and solve a recurrence relation foF de482 Chapter 10. Recurrence Relations Figure 10.16 13, a) For the binary string 001110, there are three runs: (0, 111, and 0. Meanwhile, the string OD011T has only two runs: 000 and 111: while te string 010101 determines the six runs: 0, 1,0, 1,0, 1. For = 1, we consider two Binary strings, namely, 0 and 1 — these two strings (of length 1) termine a total of swo runs. There are four binary tring of length n ~ 2 and these stings determine 1 (For 00) + 2 (for 01) = 2 (for 10) +1 (lor 11) = 6 run Find and solve a recurrence relation fr fy the total numberof runs deter- mined by the 2* binary stings of length n, where n> 1 bb) Answer the question posed in par (a) for quaternary strings of length n-(Here the alphabet comprises. 1, 2, 3) © Generalize the results of parts (2) and (b) 14. a) For n> 1, the mth triangular number tis defined by ty = 142 o chm min + 1/2. Find and solve a re- ‘curence relation for 2 1, Where 5, gy the sum of the firs » tangular numbers. [The reader ‘may wish to compare the result obtained here withthe for- 104 The Method of Generating Functions ‘mula given in Example 4.5 or with the result requested in par (b) of Exercise 8 of Section 95.) ») In an organic laboratory, Kelsey synthesizes a ery talline stractare that is made up of 10,000,000 teiangular layers of atoms. The first layer of the structure has one atom, the second layer has three toms, nd in general the inh layer has 1-42 +--+ =f, atoms. (Consider each layer, other than the las, a it were placed upon the spaces ‘that result among the neighboring atoms ofthe succeeding layer. See Fig. 10.16, (i) How many’ atoms are dere in ‘ne ofthese exystalline structures? (i) How many atoms are packed (strietly) between the 10,000th and 100,000 layer? 15, Write 2 computer program (oF develop an algorithm) to solve the problem of the Towers of Hani, Form € Z" the p= _gram should provide the necessary steps for transferring the n disks from peg 1 to peg 3 under the restrictions specitied in Example 10.28 ‘With all the different cases we had to consider for the nonhomogeneous linear recurrence relation, we now get some assistance from the generating function, This technique will find both the homogeneous and the particular solutions for aq, and it will incorporate the given initial conditions as well. Furthermore, we'll be able to do even more with this method. EXAMPLE 10.38 ‘We demonstrate the method in the following examples, Solve the relation ay ~ 34-1 =m. = Ig = 1 ‘This relation represents an infinite set of equations: =p (ns2 ay — Bay = 1104 The Method of Generating Functions 4B Multiplying the first ofthese equations by x, the second by x2, and so on, we obtain (= 1) aux! ~3agx? = Ix! (m= 2) ayn? = Baya? = 2x? Adding this second set of equations, we find that o ‘We want to solve for ay in terms of m. To accomplish this, let f(x) = 2725 dax” be the (ordinary) generating function for the sequence ay, a, a2 ‘Then Eq. (1) can be re- a Since OP) @y-1x"! = Py aux" = F(x) and a = 1, the left-hand side of Eq. (2) becomes (F(x) — 1) ~ 3xf60) Before we can proceed, we need the generating function forthe sequence 0, 1, 2,3, Recall from part (c) of Example 9.5 that (F09) = ay) ~ 3x > XEWHIE HH, 80 a ye @)—1)—3af@)= 3, and fe) = U@)-)-afed= FF feo) Using a partial fraction decomposition, we find that ie ieeaes reesei ees eeeeerreeeiGeae = 3x) RHE x = ACI ~ x)(1 —3x) + BU ~ 3x) + CU — x) From the following assignments for x, we get @=) (3) (2=0) ‘Therefore, 1 ey, 12) 1-3 =x) * =»! ays) 14), (1/2) 0-39 "G-9 * =F We tind a, by determining the coefficient of x" in each of the three summands. Fa) =484 —— Chapter 10. Recurrence Relations a) (7/4)/(1 = 3x) = AYE = 3001 = C/A + G8) + Gx}? + Gx ++], and the coefficient of a is (7/4)3". b) (1/4/01 — x) = 1/4)[L 4x 427 +---], and the coefficient of x" here is (1/4). ©) (“1/2/01 = x (-1/24(1 = x} U2 [(0) + ao + Gan? + Gon" +] and the coefficient of x" is given by (—1/2)()(-1)" CH= 1/20 +0, ‘Therefore ay = (7/4)3" — (1/2)n ~ (3/4). = O. (Note that there is nos hhere with ay”. Also, the same answer is obtained by using the techniques of Section 10.3.) UDG!) In our next example we extend what we learned in Example 10.38 10 a second-order relation. This time we present the solution within a list of instructions one can follow in ‘order to apply the generating-function method, Consider the recurrence relation EXAMPLE 10.39 gy — Sains + 6g = nz0, a= 1) We first multiply this given relation by x" because +2 is the largest subscript, that appears. This gives us aint 2 4 Gaga = 2x84? Say" 2) Then we sum all of the equations represented by the result in step (1) and obtain Front? Sagas 46S Sagat 2 Soa = ot Ef = 3) In order to have each of the subscripts on a match the corresponding exponent on. wwe rewrite the equation in step (2)as Here we also rewrite the power series on the right-hand side of the equation ina form that will permit us to ase what we learned in Section 2 of Chapter 9. 4) Let (0) = Xo ae” be the generating function forthe soluroA~The equation in step (3) now takes the form (£0) ~ ay ~ 41x) ~ SxCF(X) ~ a9) +627 FO) (f(x) = 3 = Tx) = Sef) = 3) +? FCEXAMPLE 10.40 04 The Method of Generating Functions 485 8) Solving for f(x) we have 2x? _ 3a + 100? (151460) f(a) 3 Be = SE from which it follows that A pantal-fraction decomposit gives us (by hand, or via a computer algebra system) £@ ‘Consequently, ay = 2(3") +1. = 0. We consider a third example, which has a familiar result, Lot m EN. For r > 0, let a(n,r) ~ the number of ways we can select, with repetitions allowed, r objects from a set of m dstint objects. Form > Ile (by, ba, «by be the set ofthese objects, and consider object by. Exactly cone of two things ean happen. a) The object hy is never selected. Hence the r objects are selected from (b>, This we can do in a(n ~ 1, r) ways. ) The object by is selected at least once. Then we must seleet r— 1 objects from 6), b:, .-., byl, $0 we can continue to select by in addition 10 the one selection of it we've already made, There are a(n, r — 1) ways to accomplish this. Thena(n, r) = ain — 1.7} +a(n, 7 ~ 1) because these two cases coverall possibilities and are mutually disjoint = D8, a(n, r)x" be the generating function for the sequence a(n. 0).a(n. 1). {Here fy is an abbreviation for f,(x).] From a(n, r) = a(n = Iyr) + ‘a(n, r ~ 1), where m > Land > 1, it follows that a(n." (n= Lr ta(nsr = Dx? and Realizing that a(n, 0) = 1 for n =O and a{0, r) = 0 for r > 0, we write fos ale ~ 1,0) x ater Da, Jn ~a(n, 0) Soy ~ 1+ fue Theretne, fy = tf = fits 8 fy = foi). 5, for example, then le ianefeeaieeih fi SS ag d=) =) > =F =) a fo 1 a= Oa since fo = a(0, 0) +.a(0, Dx +000, 247 +++ = 10404486 Chapter 10 Recurrence Relations Ingeneral, fe = 1/1 — 2)" = (1 — x)", soa(n, 7) isthe coefficient of x"in (1 —x)°*, which is CYC" = (72-3), {Here we dealt with a recurrence relation for a(n. 7), «discrete function of the two (integer variables nr = 0) ‘Our last example shows how generating functions may be used to solve a system of recurrence relations, ‘This example provides an approximate model forthe propagation of high- and low-energy neutronsas they stike the nuclei of issionable material (such as uranium) and are absorbed Here we deal with a fast reactor where there is no moderator (such as water). (In reality, all the neutrons have fairly high energy and there are not just two energy levels. There isa ‘continuous spectrum of energy levels, and these neutrons at the upper end of the spectrum ‘are called the high-energy neutrons. The higher-energy neutrons tend to produce more new neutrons than the lower-energy ones.) ‘Consider the reactor at time 0 and suppose one high-energy neutron is injected into the system, During each time interval thereafter (about 1 microsecond, or 10° second) the following events occur 1) When a high-energy neutron interacts with a nucleus (of fissionable material), upon absorption this results (one microsecond later) in two new high-energy neutrons and ‘one low-energy one. 1b) For interactions involving a low-energy neutron, only one neutron of each energy level is produced. Assuming tha all free neutrons interact with nuclei one microsecond after their creation, find functions of m such that ‘dq = the number of high-energy neutrons, >, = the number of low-energy neutrons, in the reactor after n microseconds, n > 0. Here we have ay = 1, by = Oand the system of recurrence relations igs = ay + by 8 best tin + be: “ Let FO) = Yeo tnx", 802) = Leg bnx™ be the generating functions for the se- ‘quences {ay|n > 0}, (by|n > 0}, respectively. From Eqs. 3) and (4), when n > 0 yg xl = Daye" byt ey byte = aga t bya ey Summing Eq, (3)' over all n > 0, we have eee ae Yeast w= Yoanst +2 bas wy105 ASpecia Kind of Nonlinear Recutence Relation (Optional) 487 In«roducing the generating functions at this point, we get F(R) ~ ay = 2x f(x) +280) ey (0) = by = xf) +2860), ay a system of equations relating the generating functions. Solving this system, we find that GA )-GG) « 0) tet (a) where 3-3 GAP BICEY YY ED ee = mem (057 2. Here ain, r) =0 when r > 1, Use the recurrence na relation a(n, r) = ain = 1p = 1 bate ~ Lr), where n= 1 and r > 1, 0 shove that f(2) = (1-+x)" generates alin) 1. Solve the following recurrence relations by the method of fs g generating functions eae 3, Solve the following systems of recurrence relations 8) dsr Oy = 3%, n=O, y= : ae DY agg) ay =, MEO, a= 1 eee ess — Her + 2de =O 20, y=, ay = 6 mZ0, a= 1, by=0 8) ggg ~ Degg + oy =P, M20, y= My gy a 2. For distinc objects, let a(n, r) denote the number of ways 2b 1 we can select, without repetition, r of the m objects when O. b=1 10.5 A Special Kind of Nonlinear Recurrence Relation (Optional) ‘Thus far our study of recurrence relations has dealt with linear relations with constant coefficients. The study of nonlinear recurrence relations and of relations with variable coefficients is not a topic we shall pursue except for one special nonlinear relation that lends itself tothe method of generating functions. ‘We shall develop the method in a counting problem on data structures. Before do ing s0, however, we first observe that if f(x) = Joey aux’ Is the generating function for ao, aj, ax... then [fGX)]? generates ayn, dod + ayo, dyads + aya + 23d,988 Chapter 10. Recurrence Réations EXAMPLE 10.42 Figure 10.7 ity + yay) $y 2 $+ 4-40} + agdg, «5 the convolution of the sequence ay, ay, 3, With itself. In Sections 3.4 and 5.1, we encountered the idea of a tree diagram. In general, a tree is an undirected graph that is connected and has no loops or cycles, Here we examine rooted binary trees. In Fig. 10.17 we see two such trees, where the circled vertex denotes the roor. These trees tare called binary because from each vertex there are at most two edges (called branches) descending (since a rooted tree isu directed graph) from that vertex, In particular, these rooted binary trees are ordered in the sense that a leftbranch descend ing from a vertex is considered different from a right branch descending from that vertex. For the case of three vertices, the five possible ordered rooted binary trees are shown in Fig. 10.18. (If no attention were paid to order, then the last four rooted trees would be the same structure.) ee » 2 Figure 1038 Our objective is to count, for n > 0, the number b, of rooted ordered binary trees on n vertices. Assuming that we know the values of b; for 0-< i input stack Figure 10.20