The Golden Ratio, Fibonacci Numbers, And Other RecurrencesLeonardo FibonacciInductive Definition or Recurrence Relation for the Fibonacci NumbersSneezwort (Achilleaptarmica)Counting PetalsPineapple whorlsBernoulli Spiral When the growth of the organism is proportional to its sizeBernoulli Spiral When the growth of the organism is proportional to its sizeGolden Ratio: the divine proportionDefinition of (Euclid)Expanding RecursivelyContinued Fraction RepresentationContinued Fraction RepresentationRemember?Continued Fraction Representation1,1,2,3,5,8,13,21,34,55,….Continued fraction representation of a standard fractione.g., 67/29 = 2 with remainder 9/29 = 2 + 1/ (29/9)A Representational CorrespondenceEuclid’s GCD = Continued FractionsSequences That Sum To nSequences That Sum To nSequences That Sum To nSequences That Sum To nSequences That Sum To nSequences That Sum To nFibonacci Numbers AgainVisual Representation: TilingVisual Representation: TilingVisual Representation: Tilingfn+1 = fn + fn-1Fibonacci IdentitiesFm+n+1 = Fm+1 Fn+1 + Fm Fn (Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)n-1More random factsThe Fibonacci QuarterlyHow to divide polynomials?The Geometric SeriesThe Infinite Geometric SeriesSomething a bit more complicatedHenceGoing the Other WayGoing the Other WayThusLinear factors on the bottomGeometric Series (Quadratic Form)Geometric Series (Quadratic Form)Power Series Expansion of FSome simple power seriesAl-Karaji’s IdentitiesCoefficient of Xk in PV = (X2+X)(1-X)-4 is the sum of the first k squares:Polynomials give us closed form expressionsREFERENCESStudy BeeThe Golden Ratio, Fibonacci Numbers, And Other RecurrencesGreat Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2006Lecture 13 October 10, 2006 Carnegie Mellon UniversityLeonardo FibonacciIn 1202, Fibonacci proposed a problem about the growth of rabbit populations.Inductive Definition or Recurrence Relation for theFibonacci NumbersStage 0, Initial Condition, or Base Case:Fib(0) = 0; Fib (1) = 1Inductive RuleFor n>1, Fib(n) = Fib(n-1) + Fib(n-2)n 01 234567Fib(n) 01 1 235813Sneezwort (Achilleaptarmica)Each time the plant starts a new shoot it takes two months before it is strong enough to support branching.Counting Petals5 petals: buttercup, wild rose, larkspur,columbine (aquilegia) 8 petals: delphiniums 13 petals: ragwort, corn marigold, cineraria,some daisies 21 petals: aster, black-eyed susan, chicory 34 petals: plantain, pyrethrum 55, 89 petals: michaelmas daisies, theasteraceae family.Pineapple whorlsChurch and Turing were both interested in the number of whorls in each ring of the spiral. The ratio of consecutive ring lengths approaches the Golden Ratio.Bernoulli Spiral When the growth of the organism is proportional to its sizeBernoulli Spiral When the growth of the organism is proportional to its sizeIs there life after π and e?Golden Ratio: the divine proportionφ= 1.6180339887498948482045…“Phi” is named after the Greek sculptor Phidiasφφφφφφ===−= − = =−−=ACABABBCACBCACBCABBCBCBC110222Definition of φ (Euclid)Ratio obtained when you divide a line segment into two unequal parts such that the ratio of the whole to the larger part is thesame as the ratio of the larger to the smaller.ABCExpanding Recursivelyφφφφ=+=++=+++111111111111Continued Fraction Representationφ=++++++++++1111111111111111111 ....Continued Fraction Representation1111111111111111111 ....152=+++++++++++Remember?We already saw the convergents of this CF[1,1,1,1,1,1,1,1,1,1,1,…]are of the formFib(n+1)/Fib(n)n115lm2i→∞−+=φ=nnFFHence:Continued Fraction Representationφ=++++++++++1111111111111111111 ....1,1,2,3,5,8,13,21,34,55,….2/1 = 23/2 = 1.55/3 = 1.666…8/5 = 1.613/8 = 1.62521/13 = 1.6153846…34/21 = 1.61904…φ = 1.6180339887498948482045Continued fraction representation of a standard fraction67 121293142=+++e.g., 67/29 = 2 with remainder 9/29= 2 + 1/ (29/9)67 1 1 122229 2 1293319942=+ =+ ++++A Representational Correspondence67 1 1 122229 2 1293319942=+ =+ ++++Euclid(67,29) 67 div 29 = 2Euclid(29,9) 29 div 9 = 3Euclid(9,2) 9 div 2 = 4Euclid(2,1) 2 div 1 = 2Euclid(1,0)Euclid’s GCD = Continued FractionsEuclid(A,B) = Euclid(B, A mod B)Stop when B=01modAABBBAB⎢⎥=+⎢⎥⎣⎦Theorem: All fractions have finite continuous fraction expansionsLet us take a slight detour and look at a different representation.Sequences That Sum To nLet fn+1be the number of different sequences of 1’s and 2’s that sum to n.Example: f5= 5Sequences That Sum To nLet fn+1be the number of different sequences of 1’s and 2’s that sum to n.Example: f5= 54 = 2 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1Sequences That Sum To nf1f2f3Let fn+1be the number of different sequences of 1’s and 2’s that sum to n.Sequences That Sum To nf1= 10 = the empty sumf2= 11 = 1f3= 22 = 1 + 12Let fn+1be the number of different sequences of 1’s and 2’s that sum to n.Sequences That Sum To nfn+1= fn+ fn-1Let fn+1be the number of different sequences of 1’s and 2’s that sum to n.Sequences That Sum To nfn+1= fn+ fn-1Let fn+1be the number of different sequences of 1’s and 2’s that sum to n.# of sequences beginning with a 2# of sequences beginning with a 1Fibonacci Numbers Againffn+1n+1= f= fnn+ f+ fnn--11ff11= 1 f= 1 f22= 1= 1Let fn+1be the number of different sequences of 1’s and 2’s that sum to n.Visual Representation: TilingLet fn+1be the number of different ways to tile a 1 × n strip with squares and dominoes.Visual Representation: TilingLet fn+1be the number of different ways to tile a 1 × n strip with squares and dominoes.Visual Representation: Tiling1 way to tile a strip of length 01 way to tile a strip of length 1:2 ways to tile a strip of length 2:fn+1= fn+ fn-1fn+1is number of ways to tile length n.fntilings that start with a square.fn-1tilings that start with a domino.Let’s use this visual representation to prove a couple of Fibonacci identities.Fibonacci IdentitiesSome examples:F2n= F1+ F3+ F5+ … + F2n-1Fm+n+1= Fm+1Fn+1+ FmFn(Fn)2= Fn-1Fn+1+ (-1)nFm+n+1= Fm+1Fn+1+ FmFnmmnnmm--11nn--11(Fn)2= Fn-1Fn+1+ (-1)n(Fn)2= Fn-1Fn+1+ (-1)nnn--11Fntilings of a strip of length n-1(Fn)2=
View Full Document
Unlocking...