Great Theoretical Ideas In Computer Science V Adamchik D Sleator Lecture 8 CS 15 251 Feb 04 2010 Spring 2010 Carnegie Mellon University Recurrences and Continued Fractions Solve in integers x1 x2 x5 40 xk k yk xk k y1 y2 y5 25 yk 0 29 4 Solve in integers x y z 11 x 0 0 y 3 z 0 X11 1 x x2 x3 1 x 2 Partitions Find the number of ways to partition the integer n 3 1 1 1 1 2 4 1 1 1 1 1 1 2 1 3 2 2 1x1 2x2 3x3 nxn n 1 1 x 1 x2 1 x3 1 xn Plan Review Sat 6 8pm in 2315 DH Exam Mon in recitations Characteristic Equations Golden Ratio Continued Fractions Applied Combinatorics by Alan Tucker The Divine Proportion by H E Huntley Leonardo Fibonacci In 1202 Fibonacci has become interested in rabbits and what they do 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 old Fn of rabbit pairs at the beginning of the nth month month 1 2 3 4 5 6 rabbits 1 1 2 3 5 8 7 1 3 F0 0 F1 1 Fn Fn 1 Fn 2 for n 2 What is a closed form formula for Fn We won t be using GFs WARNING This lecture has explicit mathematical content that can be shocking to some students Characteristic Equation Fn Fn 1 Fn 2 Consider solutions of the form Fn n for some unknown constant 0 must satisfy n n 1 n 2 0 n n 1 n 2 0 iff n 2 2 1 0 iff 2 1 0 Characteristic equation 1 5 2 or 1 phi is the golden ratio a b a n b 1 n satisfies the inductive condition So for all these values of the inductive condition is satisfied 2 1 0 Do any of them happen to satisfy the base condition as well F0 0 F1 1 a b a n b 1 n satisfies the inductive condition Adjust a and b to fit the base conditions n 0 a b 0 n 1 a 1 b 1 1 1 1 a 5 1 b 5 Leonhard Euler 1765 n n 1 Fn 5 1 5 2 Fibonacci Power Series F x k k k 0 x 2 1 x x Fibonacci Bamboozlement 8 8 13 5 Cassini s Identity Fn 1Fn 1 Fn2 1 n We dissect FnxFn square and rearrange pieces into Fn 1xFn 1 square Heads on How to convert kilometers into miles Magic conversion 50 km 34 13 3 50 F9 F7 F4 F8 F6 F3 31 miles From the previous lecture dn dn 1 2dn 2 d0 0 d1 1 Characteristic Equation dn dn 1 2dn 2 d0 0 d1 1 1 1 2 2 2 2 0 n n dn a 1 b 2 a b n n dn a 1 b 2 0 0 d0 0 a 1 b 2 a b 1 1 d1 1 a 1 b 2 a 2 b 1 1 b a 3 3 Characteristic Equation xn 2xn 1 xn 2 x0 1 x1 2 2 2 1 0 1 2 1 Characteristic Equation Theorem Let be a root of multiplicity p of the characteristic equation Then n n 2 n p 1 n n n n are all solutions xn 2xn 1 xn 2 The theorem says that xn n is a solution This can be easily verified n 2 n n From the previous lecture Rogue Recurrence an 5an 1 8an 2 4an 3 a0 0 a1 1 a2 4 Characteristic equation 3 2 5 8 4 0 1 1 2 3 2 an 5an 1 8an 2 4an 3 a0 0 a1 1 a2 4 General solution an n n a b 2 c n 2 a0 0 a b a1 1 a 2b 2c a2 4 a 4b 8c a b 0 1 c 2 n 1 an n 2 The Golden Ratio Some other majors have their mystery numbers like and e In Computer Science the mystery number is the Golden Ratio S Rudich Golden Ratio Divine Proportion 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 AC AB AC AB BC BC 2 A B 1 0 AC AB AC AB 1 BC BC BC 2 2 C Golden Ratio the divine proportion 2 1 0 1 5 2 1 6180339887498948482045 Phi is named after the Greek sculptor Phidias 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 The Golden Ratio 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 salvation the list must end here Luca Pacioli Divina Proportione Luca Pacioli 1509 Ninth Most Excellent Effect two diagonals of a regular pentagon divide each other in the Divine Proportion C B A AC AB AB BC Expanding Recursively 2 1 0 1 1 1 1 1 1 Expanding Recursively 1 1 1 1 1 1 1 1 A Simple Continued Fraction Is Any Expression Of The Form a b c d e 1 1 1 1 1 f 1 1 g 1 h 1 i j where a b c are whole numbers A Continued Fraction can have a finite or infinite number of terms a b c d e 1 1 1 1 1 f 1 1 g 1 h 1 i j We also denote this fraction by a b c d e f Continued Fraction Representation 8 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 0 0 0 Recursively Defined Form For CF CF wholenumber 1 wholenumber CF Proposition Any finite continued fraction evaluates to a rational Converse Any rational has a finite continued fraction representation Euclid s GCD Continued Fraction Euclid A B Euclid B A mod B Stop when B 0 a b q1 r1 b r1 q2 r2 r1 r2 q3 r3 rk 1 rk qk 1 0 Euclid s GCD Continued Fraction a b q1 r1 b r1 q2 r2 r1 r2 q3 r3 rk 1 rk qk 1 0 a r1 1 q1 q1 b b b r1 b r2 1 q2 q2 …
View Full Document
Unlocking...