DOC PREVIEW
Module 17 Recurrences

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

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


Module 17 Recurrences

Download Module 17 Recurrences
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Module 17 Recurrences and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Module 17 Recurrences 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?