Rabbits, Continued Fractions, The Golden Ratio, and Euclid’s GCDLeonardo FibonacciSlide 3Slide 4The rabbit reproduction modelSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Inductive Definition or Recurrence Relation for the Fibonacci NumbersSlide 13A (Simple) Continued Fraction Is Any Expression Of The Form:A Continued Fraction can have a finite or infinite number of terms.A Finite Continued FractionA Infinite Continued FractionRecursively Defined Form For CFAncient Greek Representation: Continued Fraction RepresentationSlide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Continued Fraction RepresentationQuadratic EquationsSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 381.6180339887498948482045…..KhufuGreat Pyramid at GizehSlide 42Golden Ratio Divine ProportionParthenon, Athens (400 B.C.)PentagonRatio of height of the person to the height of a person’s navelDefinition of (Euclid)Slide 48The Divine QuadraticExpanding RecursivelySlide 51Slide 52Slide 53Slide 54We already know that the convergents of this CF have the form Fib(n+1)/Fib(n)Slide 561,1,2,3,5,8,13,21,34,55,….Slide 58Slide 59Grade School GCD algorithmSlide 61Slide 62Slide 63Ancient Recursion Euclid’s GCD algorithmGCD(67,29) = 1Euclid’s GCD CorrectnessEuclid’s GCD TerminationSlide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74EUCLID(A,B) // requires AB0 If B=0 then Return A else Return Euclid( B, A mod B)Let <r,s> denote the number r*67 + s*29 . Calculate all intermediate values in this representation.Euclid’s Extended GCD algorithm Input: X,Y Output: r,s,d such that rX+sY = d = GCD(X,Y)Euclid’s GCD algorithmSlide 79Lame: T(Fk) = k [1845]Lemma: Euclid(Fk+1,Fk) makes k recursive callsLemma: Euclid(Fk+1,Fk) makes k recursive callsSlide 83Slide 84 k 2, Euclid(A,B) makes k calls A Fk+1 and B FkSlide 86Slide 87Slide 88Continued fraction representation of a standard fraction67/29 = 2 with remainder 9/29 = 2 + 1/ (29/9)A Representational CorrespondenceEuclid’s GCD = Continued FractionsTheorem: All fractions have finite continuous fraction expansionsFibonacci Magic TrickAnother Trick!REFERENCESRabbits, Continued Fractions, The Golden Ratio, and Euclid’s GCDGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 6 Jan 29, 2004 Carnegie Mellon University3 13 13123131313131313133 ....+= ++++++++++Leonardo FibonacciIn 1202, Fibonacci proposed a problem about the growth of rabbit populations.Leonardo FibonacciIn 1202, Fibonacci proposed a problem about the growth of rabbit populations.Leonardo FibonacciIn 1202, Fibonacci proposed a problem about the growth of rabbit populations.The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813The 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 7rabbits1 1 2 3 5 813Inductive Definition or Recurrence Relation for theFibonacci Numbers Stage 0, Initial Condition, or Base Case:Fib(1) = 1; Fib (2) = 1Inductive RuleFor n>3, Fib(n) = Fib(n-1) + Fib(n-2)n 0 1 2 3 4 5 6 7Fib(n) % 1 1 2 3 5 813Inductive Definition or Recurrence Relation for theFibonacci Numbers Stage 0, Initial Condition, or Base Case:Fib(0) = 0; Fib (1) = 1Inductive RuleFor n>1, Fib(n) = Fib(n-1) + Fib(n-2)n 0 1 2 3 4 5 6 7Fib(n) 0 1 1 2 3 5 813A (Simple) Continued Fraction Is Any Expression Of The Form:111111111....abcdefghij++++++++++where a, b, c, … are whole numbers.A Continued Fraction can have a finite or infinite number of terms.111111111....abcdefghij++++++++++We also denote this fraction by [a,b,c,d,e,f..]A Finite Continued Fraction1213142+++Also denoted [2.3.4.2.0,0,0,0,0,…]A Infinite Continued Fraction1112121212121212122 ....++++++++++Also denoted [1,2,2,2,….Recursively Defined Form For CFCF whole number, or 1 = whole numberCF=+Ancient Greek Representation:Continued Fraction Representation67 121293142= +++Ancient Greek Representation:Continued Fraction Representation5 111312= ++Ancient Greek Representation:Continued Fraction Representation5 11131111= +++= [1,1,1,1,0,0,0,…]Ancient Greek Representation:Continued Fraction Representation1? 11111111= ++++Ancient Greek Representation:Continued Fraction Representation8 1115111111= ++++Ancient Greek Representation:Continued Fraction Representation13 111811111111= +++++Let r1 = [1,0,0,0..]r2= [1,1,0,0,0….r3 = [1,1,1,0,0…and so on.Theorem: rn = Fib(n+1)/Fib(n)Proposition: Any finite continued fraction evaluates to a rational.Theorem (proof later):Any rational has a finite continued fraction.Continued Fraction
View Full Document