Recurrences and Continued FractionsSlide 2Slide 3Slide 4Slide 5Leonardo FibonacciThe rabbit reproduction modelSlide 8Slide 9Characteristic Equationn - n-1 - n-2 = 0Slide 12a,b a n + b (-1/)n satisfies the inductive conditionSlide 14Slide 15Fibonacci BamboozlementCassini’s IdentityHeads-onSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27The Golden RatioGolden Ratio -Divine ProportionGolden Ratio - the divine proportionAestheticsWhich is the most attractive rectangle?Slide 33The Golden RatioDivina Proportione Luca Pacioli (1509)Table of contentsSlide 37Slide 38Expanding RecursivelySlide 40A (Simple) Continued Fraction Is Any Expression Of The Form:A Continued Fraction can have a finite or infinite number of terms.Continued Fraction RepresentationRecursively Defined Form For CFSlide 45Euclid’s GCD = Continued FractionSlide 47Slide 48A Pattern for Divine ProportionQuadratic EquationsA Periodic CFA period-2 CFSlide 54Slide 55Slide 56What is the pattern?Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64CF for ApproximationsSlide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Recurrences and Continued Recurrences and Continued FractionsFractionsGreat Theoretical Ideas In Computer ScienceGreat Theoretical Ideas In Computer ScienceV. AdamchikV. AdamchikD. SleatorD. SleatorCS 15-251 Spring CS 15-251 Spring 20102010Lecture 8Lecture 8Feb 04, 2010Feb 04, 2010Carnegie Mellon Carnegie Mellon UniversityUniversitySolve in integersx1 + x2 +…+ x5 = 40xkk; yk=xk – ky1 + y2 +…+ y5 = 25yk≥ 0; 429Solve in integersx + y + z = 11x0; 0y 3; z0232 x)- (1xxx1 [X11]Find the number of ways to partition the integer n3 = 1+1+1 = 1+24 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2Partitions nnx3x2x1xn321 ...)x- )...(1x- )(1x- x)(1- (1n321Plan•Review: Sat, 6-8pm in 2315 DH•Exam: Mon in recitations •Characteristic Equations•Golden Ratio•Continued FractionsApplied Combinatorics, by Alan TuckerThe Divine Proportion, by H. E. HuntleyLeonardo FibonacciIn 1202, Fibonacci has become interested in rabbits and what they doThe rabbit reproduction model•A rabbit lives forever•The population starts as a single newborn pair•Every month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth monthmonth 1 2 3 4 5 6 7rabbits 1 1 2 3 5 813What is a closed form formula for Fn?F0=0, F1=1, Fn=Fn-1+Fn-2 for n≥2 We won’t be using GFs!This lecture has explicit mathematical content that can be shocking to some students.WARNING!!!!Characteristic Equation Fn = Fn-1 + Fn-2Consider solutions of the form: Fn= n for some (unknown) constant ≠ 0 must satisfy: n - n-1 - n-2 = 0n - n-1 - n-2 = 0iff iff n-2(2 - - 1) = 0iff 2 - - 1 = 0251Characteristic equation = , or = -1/ (“phi”) is the golden ratioSo for all these values of the inductive condition is satisfied: 2 - - 1= 0Do any of them happen to satisfy the base condition as well? F0=0, F1=1a,b a n + b (-1/)n satisfies the inductive conditiona,b a n + b (-1/)n satisfies the inductive conditionAdjust a and b to fit the base conditions.n=0: a + b = 0n=1: a 1 + b (-1/ )1 = 151b ,51a Leonhard Euler (1765)5)1(Fnnn251Fibonacci Power Series ??0kkkxF21 xxxFibonacci Bamboozlement88135Cassini’s Identity Fn+1Fn-1 - Fn2 = (-1)nWe dissect FnxFn square and rearrange pieces into Fn+1xFn-1 squareHow to convert kilometers into miles?Heads-on50 km = 34 + 13 + 3Magic conversionF8 + F6 + F3 = 31 miles50 = F9 + F7 + F4From the previous lecture1d 0,d2ddd102n1nnCharacteristic Equation1d 0,d2ddd102n1nn0222,121nnn2 b1)( ad a, bnnn2 b1)( ad ba2 b1)( a0d000b 2a2 b1)( a1d11131a,31b Characteristic Equation2x 1,xx2xx102n1nn0122121Characteristic EquationTheorem. Let be a root of multiplicity p of the characteristic equation. Then n1-pn2nnλn,...,λn,λn ,λare all solutions.2n1nnx2xxThe theorem says that xn=n is a solution.This can be easily verified: n = 2 n - nFrom the previous lecture:Rogue Recurrence4a 1,a 0,a4a8a5aa2103n2n1nn048523Characteristic equation:2,13214a 1,a 0,a4a8a5aa2103n2n1nnnnn2 n c2 b aa General solution:8c4ba4a2c2ba1ab a0a21021c0,ba1-nn2 na The Golden Ratio “Some other majors have their mystery numbers, like and e. In Computer Science the mystery number is , the Golden Ratio.” – S.RudichGolden Ratio -Divine ProportionRatio obtained when you divide a line segment into two unequal parts such that the ratio of the whole to the larger part is the same as the ratio of the larger to the smaller.BCABABACBCACBCABABAC21BCABACBCABBCAC2ABC012Golden Ratio - the divine proportion = 1.6180339887498948482045…“Phi” is named after the Greek sculptor Phidias012251Aesthetics plays a central role in renaissance art and architecture.After measuring the dimensions of pictures, cards, books, snuff boxes, writing paper, windows, and such, psychologist Gustav Fechner claimed that the preferred rectangle had sides in the golden ratio (1871).Which is the most attractive rectangle?Which is the most attractive Which is the most attractive rectangle?rectangle?Golden Rectangle1The Golden RatioDivina ProportioneLuca Pacioli (1509)Pacioli devoted an entire book to the marvelous properties of . The book was illustrated by a friend of his named:Leonardo Da VinciTable of contents•The first considerable effect•The second essential effect•The third singular effect•The fourth ineffable effect•The fifth admirable effect•The sixth inexpressible effect•The seventh inestimable effect•The ninth most excellent effect•The twelfth incomparable effect•The thirteenth most distinguished effectTable of contents“For the sake of salvation, the list must end here” – Luca PacioliDivina ProportioneLuca Pacioli (1509)"Ninth Most Excellent Effect" two
View Full Document