Great Theoretical Ideas In Computer Science John Lafferty Lecture 13 CS 15 251 October 10 2006 Fall 2006 Carnegie Mellon University The Golden Ratio Fibonacci Numbers And Other Recurrences Leonardo Fibonacci In 1202 Fibonacci proposed a problem about the growth of rabbit populations Inductive Definition or Recurrence Relation for the Fibonacci Numbers Stage 0 Initial Condition or Base Case Fib 0 0 Fib 1 1 Inductive Rule For n 1 Fib n Fib n 1 Fib n 2 n 0 1 2 3 4 5 6 7 Fib n 0 1 1 2 3 5 8 1 3 Sneezwort Achilleaptarmica Each time the plant starts a new shoot it takes two months before it is strong enough to support branching Counting Petals 5 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 the asteraceae family Pineapple whorls Church 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 size Bernoulli Spiral When the growth of the organism is proportional to its size Is there life after and e Golden Ratio the divine proportion 1 6180339887498948482045 Phi is named after the Greek sculptor Phidias Definition 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 the same as the ratio of the larger to the smaller AC AB AB BC A AC 2 BC AC AB BC 2 1 BC BC BC 2 1 0 B C Expanding Recursively 1 1 1 1 1 1 1 1 1 1 1 1 Continued Fraction Representation 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Continued Fraction Representation 1 5 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Remember We already saw the convergents of this CF 1 1 1 1 1 1 1 1 1 1 1 are of the form Fib n 1 Fib n Fn 1 5 f Hence limn Fn 1 2 Continued Fraction Representation 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 5 8 13 21 34 55 2 1 3 2 5 3 8 5 13 8 21 13 34 21 2 1 5 1 666 1 6 1 625 1 6153846 1 61904 1 6180339887498948482045 Continued fraction representation of a standard fraction 67 1 2 1 29 3 1 4 2 67 1 1 1 2 2 2 29 2 1 29 3 3 1 9 9 4 2 e g 67 29 2 with remainder 9 29 2 1 29 9 A Representational Correspondence 67 1 1 1 2 2 2 29 2 1 29 3 3 1 9 9 4 2 Euclid 67 29 Euclid 29 9 Euclid 9 2 Euclid 2 1 Euclid 1 0 67 div 29 29 div 9 9 div 2 2 div 1 2 3 4 2 Euclid s GCD Continued Fractions A A B B 1 B A mod B Euclid A B Euclid B A mod B Stop when B 0 Theorem All fractions have finite continuous fraction expansions Let us take a slight detour and look at a different representation Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n Example f5 5 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n Example f5 5 4 2 2 2 1 1 1 1 2 1 1 1 1 2 1 1 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n f1 f2 f3 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n f1 1 0 the empty sum f2 1 1 1 f3 2 2 1 1 2 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n fn 1 fn fn 1 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n fn 1 fn fn 1 of sequences beginning with a 1 of sequences beginning with a 2 Fibonacci Numbers Again Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n fn 1 fn fn 1 f1 1 f2 1 Visual Representation Tiling Let fn 1 be the number of different ways to tile a 1 n strip with squares and dominoes Visual Representation Tiling Let fn 1 be the number of different ways to tile a 1 n strip with squares and dominoes Visual Representation Tiling 1 way to tile a strip of length 0 1 way to tile a strip of length 1 2 ways to tile a strip of length 2 fn 1 fn fn 1 fn 1 is number of ways to tile length n fn tilings that start with a square fn 1 tilings that start with a domino Let s use this visual representation to prove a couple of Fibonacci identities Fibonacci Identities Some examples F2n F1 F3 F5 F2n 1 Fm n 1 Fm 1 Fn 1 Fm Fn Fn 2 Fn 1 Fn 1 1 n Fm n 1 Fm 1 Fn 1 m m 1 n n 1 Fm Fn Fn 2 Fn 1 Fn 1 1 n Fn 2 Fn 1 Fn 1 1 n n 1 Fn tilings of a strip of length n 1 Fn 2 Fn 1 Fn 1 n 1 n 1 1 n Fn 2 Fn 1 Fn 1 1 n n Fn 2 tilings of two strips of size n1 Fn 2 Fn 1 Fn 1 1 n n Draw a vertical fault line at the rightmost position n possible without cutting any Fn 2 Fn 1 Fn 1 n Swap the tails at the fault line to map to a tiling of 2 n 1 s to a tiling of an n 2 and an n 1 n Fn 2 Fn 1 Fn 1 n Swap the tails at the fault line to map to a tiling of 2 n 1 s to a tiling of an n 2 and an n 1 n Fn 2 Fn 1 Fn 1 n even n odd 1 n 1 More random facts The product of any four consecutive Fibonacci numbers is the area of a Pythagorean triangle The sequence of final digits in Fibonacci numbers repeats in cycles of 60 The last two digits repeat in 300 …
View Full Document
Unlocking...