New version page

# Module 17 Recurrences

## This preview shows page 1-2-14-15-30-31 out of 31 pages.

View Full Document

End of preview. Want to read all 31 pages?

View Full Document
Unformatted text preview:

4/15/2003 (c)2001-2003, Michael P. Frank 1Module #17 - RecurrencesUniversity of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. FrankSlides for a Course Based on the TextDiscrete Mathematics & Its Applications(5thEdition)by Kenneth H. Rosen4/15/2003 (c)2001-2003, Michael P. Frank 2Module #17 - RecurrencesModule #17:Recurrence RelationsRosen 5thed., §6.1-6.3~29 slides, ~1.5 lecture4/15/2003 (c)2001-2003, Michael P. Frank 3Module #17 - Recurrences§6.1: Recurrence Relations•A recurrence relation (R.R., or just recurrence) for a sequence {an} is an equation that expresses anin terms of one or more previous elements a0, …, an−1of the sequence, for all n≥n0.– A recursive definition, without the base cases.• A particular sequence (described non-recursively) is said to solve the given recurrence relation if it is consistent with the definition of the recurrence.– A given recurrence relation may have many solutions.4/15/2003 (c)2001-2003, Michael P. Frank 4Module #17 - RecurrencesRecurrence Relation Example• Consider the recurrence relationan= 2an−1− an−2(n≥2).• Which of the following are solutions?an= 3nan= 2nan= 5YesYesNo4/15/2003 (c)2001-2003, Michael P. Frank 5Module #17 - RecurrencesExample Applications• Recurrence relation for growth of a bank account with P% interest per given period:Mn= Mn−1+ (P/100)Mn−1• Growth of a population in which each organism yields 1 new one every period starting 2 periods after its birth.Pn= Pn−1+ Pn−2(Fibonacci relation)4/15/2003 (c)2001-2003, Michael P. Frank 6Module #17 - RecurrencesSolving Compound Interest RR• Mn= Mn−1+ (P/100)Mn−1= (1 + P/100) Mn−1= rMn−1(let r = 1 + P/100)= r (rMn−2)= r·r·(rMn−3) …and so on to…= rnM04/15/2003 (c)2001-2003, Michael P. Frank 7Module #17 - RecurrencesTower of Hanoi Example• Problem: Get all disks from peg 1 to peg 2.– Only move 1 disk at a time.– Never set a larger disk on a smaller one.Peg #1 Peg #2 Peg #34/15/2003 (c)2001-2003, Michael P. Frank 8Module #17 - RecurrencesHanoi Recurrence Relation•Let Hn= # moves for a stack of n disks.• Optimal strategy:– Move top n−1 disks to spare peg. (Hn−1moves)– Move bottom disk. (1 move)– Move top n−1 to bottom disk. (Hn−1moves)• Note: Hn= 2Hn−1+ 14/15/2003 (c)2001-2003, Michael P. Frank 9Module #17 - RecurrencesSolving Tower of Hanoi RRHn= 2 Hn−1+ 1= 2 (2 Hn−2+ 1) + 1 = 22 Hn−2+ 2 + 1= 22(2 Hn−3+ 1) + 2 + 1 = 23Hn−3+ 22+ 2 + 1…= 2n−1H1+ 2n−2+ … + 2 + 1= 2n−1+ 2n−2+ … + 2 + 1 (since H1= 1)= = 2n− 1∑−=102nii4/15/2003 (c)2001-2003, Michael P. Frank 10Module #17 - Recurrences§6.2: Solving Recurrences•A linear homogeneous recurrence of degree kwith constant coefficients (“k-LiHoReCoCo”) is a recurrence of the forman= c1an−1+ … + ckan−k,where the ciare all real, and ck≠ 0.• The solution is uniquely determined if kinitial conditions a0…ak−1are provided.General Solution Schemas4/15/2003 (c)2001-2003, Michael P. Frank 11Module #17 - RecurrencesSolving LiHoReCoCos• Basic idea: Look for solutions of the form an= rn, where r is a constant.• This requires the characteristic equation:rn= c1rn−1+ … + ckrn−k, i.e., rk− c1rk−1− … − ck= 0• The solutions (characteristic roots) can yield an explicit formula for the sequence.4/15/2003 (c)2001-2003, Michael P. Frank 12Module #17 - RecurrencesSolving 2-LiHoReCoCos• Consider an arbitrary 2-LiHoReCoCo:an= c1an−1+ c2an−2• It has the characteristic equation (C.E.): r2− c1r − c2= 0• Thm. 1: If this CE has 2 roots r1≠r2, thenan= α1r1n+ α2r2nfor n≥0for some constants α1, α2.4/15/2003 (c)2001-2003, Michael P. Frank 13Module #17 - RecurrencesExample• Solve the recurrence an= an−1+ 2an−2given the initial conditions a0= 2, a1= 7.• Solution: Use theorem 1– c1= 1, c2= 2– Characteristic equation: r2− r − 2 = 0– Solutions: r = [−(−1)±((−1)2− 4·1·(−2))1/2] / 2·1= (1±91/2)/2 = (1±3)/2, so r = 2 or r = −1.–So an= α12n+ α2(−1)n.4/15/2003 (c)2001-2003, Michael P. Frank 14Module #17 - RecurrencesExample Continued…• To find α1and α2, solve the equations for the initial conditions a0and a1: a0= 2 = α120+ α2(−1)0a1= 7 = α121+ α2(−1)1Simplifying, we have the pair of equations:2 = α1+ α27 = 2α1− α2which we can solve easily by substitution:α2= 2−α1; 7 = 2α1− (2−α1) = 3α1− 2; 9 = 3α1; α1= 3; α2= 1.• Final answer: an= 3·2n− (−1)nCheck: {an≥0} = 2, 7, 11, 25, 47, 97 …4/15/2003 (c)2001-2003, Michael P. Frank 15Module #17 - RecurrencesThe Case of Degenerate Roots• Now, what if the C.E. r2− c1r − c2= 0 has only 1 root r0?• Theorem 2: Then,an= α1r0n+ α2nr0n, for all n≥0,for some constants α1, α2.4/15/2003 (c)2001-2003, Michael P. Frank 16Module #17 - Recurrencesk-LiHoReCoCos• Consider a k-LiHoReCoCo:• It’s C.E. is:• Thm.3: If this has k distinct roots ri, then the solutions to the recurrence are of the form:for all n≥0, where the αiare constants.∑=−=kiininaca101=−∑=−kiikikrcr∑==kiniinra1α4/15/2003 (c)2001-2003, Michael P. Frank 17Module #17 - RecurrencesDegenerate k-LiHoReCoCos• Suppose there are t roots r1,…,rtwith multiplicities m1,…,mt. Then:for all n≥0, where all the α are constants.∑∑=−==tinimjjjinrnai110,α4/15/2003 (c)2001-2003, Michael P. Frank 18Module #17 - RecurrencesLiNoReCoCos•Linear nonhomogeneous RRs with constant coefficients may (unlike LiHoReCoCos) contain some terms F(n) that depend onlyon n (and not on any ai’s). General form:an= c1an−1+ … + ckan−k+ F(n)The associated homogeneous recurrence relation(associated LiHoReCoCo).4/15/2003 (c)2001-2003, Michael P. Frank 19Module #17 - RecurrencesSolutions of LiNoReCoCos• A useful theorem about LiNoReCoCos:– If an= p(n) is any particular solution to the LiNoReCoCo– Then all its solutions are of the form:an= p(n) + h(n),where an= h(n) is any solution to the associated homogeneous RR)(1nFacakiinin+=∑=−=∑=−kiininaca14/15/2003 (c)2001-2003, Michael P. Frank 20Module #17 - RecurrencesExample• Find all solutions to an= 3an−1+2n. Which solution has a1= 3?– Notice this is a 1-LiNoReCoCo. Its associated 1-LiHoReCoCo is an= 3an−1, whose solutions are all of the form an= α3n. Thus the solutions to the original problem are all of

Unlocking...