Great Theoretical Ideas In Computer Science Steven Rudich Lecture 13 CS 15 251 Feb 22 2005 Spring 2005 Carnegie Mellon University The Fibonacci Numbers And An Unexpected Calculation 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 Fib n 0 1 1 2 3 5 8 7 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 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 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 2 f 1 0 5 1 f 2 The Divine Quadratic 2 f f 1 0 5 1 f 2 1 1 Expanding Recursively 1 1 Expanding Recursively 1 1 1 1 1 1 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 Best Rational Approximations to 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 61 80 33 98 Is there life after and e 87 49 8 94 84 82 04 5 Khufu 2589 2566 B C 2 300 000 blocks averaging 2 5 tons each Package Great Pyramid at Gizeh a 1 618 b a b The ratio of the altitude of a face to half the base Golden Ratio the divine proportion 1 6180339887498948482045 Phi is named after the Greek sculptor Phidias Parthenon Athens 400 B C Pentagon Golden Ratio Divine Proportion 1 6180339887498948482045 Phi is named after the Greek sculptor Phidias Ratio of height of the person to height of a person s navel Divina Proportione Luca Pacioli 1509 Pacioli devoted an entire book to the marvelous properties of The book was illustrated by a friend of his named Leonardo Da Vinci Table of contents The The The The The The The The The The first considerable effect second essential effect third singular effect fourth ineffable effect fifth admirable effect sixth inexpressible effect seventh inestimable effect ninth most excellent effect twelfth incomparable effect thirteenth most distinguished effect Table of contents For the sake of our salvation this list of effects must end Aesthetics 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 rectangle 1 Golden Rectangle Let s take a break from the Fibonacci Numbers in order to remark on polynomial division How to divide polynomials 1 1 X 1 X X2 1 X 1 1 X X X X2 X2 X2 X3 X3 1 X X2 X3 X4 X5 X6 X7 n 1 X 1 1 2 3 n 1 n 1 X X X X X X 1 The Geometric Series n 1 X 1 1 2 3 n 1 n 1 X X X X X X 1 The limit as n goes to infinity of Xn 1 1 X 1 1 X 1 1 1 X 1 X1 X2 X 3 Xn 1 1 X The Infinite Geometric Series 1 X1 X2 X 3 Xn 1 1 X X 1 1 X1 X2 X 3 Xn X1 X 2 X 3 Xn Xn 1 1 X1 X2 X 3 Xn 1 Xn Xn 1 1 1 X1 X2 X 3 Xn 1 1 X 1 X X2 1 X 1 1 X X X X2 X2 X2 X3 X3 Something a bit more complicated X X2 2X3 3X4 5X5 8X6 1 X X2 X 1 X X2 X X X2 X3 X2 X3 X2 X3 X4 2X3 X4 2X3 2X4 2X5 3X4 2X5 3X4 3X5 3X6 5X5 3X6 5X5 5X6 5X7 8X6 5X7 8X6 8X7 8X8 Hence X 1 X X2 0 1 1 X1 1 X2 2X3 3X4 5X5 8X6 F0 1 F1 X1 F2 X2 F3 X3 F4 X4 F5 X5 F6 X6 Going the Other Way 1 X X2 F0 1 F1 X1 F2 X2 Fn 2 Xn 2 Fn 1 Xn 1 Fn Xn F0 1 F1 X1 F2 X2 Fn 2 Xn 2 Fn 1 Xn 1 Fn Xn F0 X1 F1 X2 Fn 3 Xn 2 Fn 2 Xn 1 Fn 1 Xn F0 X2 Fn 4 Xn 2 Fn 3 Xn 1 Fn 2 Xn F0 1 F1 F0 X1 X F0 0 F1 1 Thus F0 1 F1 X1 F2 X2 Fn 1 Xn 1 Fn Xn X 1 X X2 I was trying to get away from them Vector Recurrence Relations Let P be a vector program that takes input A vector relation is any statement of the form V P V If there is a unique V satisfying the relation then V is said to be defined by the relation V P V Fibonacci Numbers Recurrence Relation Definition F0 0 F1 1 Fn Fn 1 Fn 2 n 1 Vector Recurrence Relation Definition F RIGHT F 1 RIGHT RIGHT F F RIGHT F 1 RIGHT RIGHT F F a0 a1 a2 a3 a4 RIGHT F 1 0 …
View Full Document
Unlocking...