Great Theoretical Ideas In Computer Science Steven Rudich Lecture 6 CS 15 251 Jan 29 2004 Spring 2004 Carnegie Mellon University Rabbits Continued Fractions The Golden Ratio and Euclid s GCD 3 13 3 2 3 1 1 1 3 1 3 1 3 1 3 1 3 1 3 1 3 3 Leonardo Fibonacci In 1202 Fibonacci proposed a problem about the growth of rabbit populations Leonardo Fibonacci In 1202 Fibonacci proposed a problem about the growth of rabbit populations Leonardo Fibonacci In 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 old Fn of rabbit pairs at the beginning of the nth month month 1 2 3 4 5 6 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 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 7 rabbit s 1 1 2 3 5 8 1 3 Inductive Definition or Recurrence Relation for the Fibonacci Numbers Stage 0 Initial Condition or Base Case Fib 1 1 Fib 2 1 Inductive Rule For n 3 Fib n Fib n 1 Fib n 2 n 0 1 2 3 4 5 6 Fib n 1 1 2 3 5 8 7 1 3 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 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 A Finite Continued Fraction 1 2 1 3 1 4 2 Also denoted 2 3 4 2 0 0 0 0 0 A Infinite Continued Fraction 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 Also denoted 1 2 2 2 Recursively Defined Form For CF CF whole number or 1 whole number CF Ancient Greek Representation Continued Fraction Representation 67 1 2 1 29 3 1 4 2 Ancient Greek Representation Continued Fraction Representation 5 1 1 1 3 1 2 Ancient Greek Representation Continued Fraction Representation 5 1 1 1 3 1 1 1 1 1 1 1 1 0 0 0 Ancient Greek Representation Continued Fraction Representation 1 1 1 1 1 1 1 1 1 Ancient Greek Representation Continued Fraction Representation 8 1 1 1 5 1 1 1 1 1 1 Ancient Greek Representation Continued Fraction Representation 13 1 8 1 1 1 1 1 1 1 1 1 1 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 Representation 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 Quadratic Equations X2 3x 1 0 3 13 X 2 X2 3X 1 X 3 1 X X 3 1 X 3 1 3 1 X Continued Fraction Representation 3 13 3 2 3 1 1 1 3 1 3 1 3 1 3 1 3 1 3 1 3 3 Conclusion Any quadratic solution has a periodic continued fraction Converse homework Any periodic continued fraction is the solution of a quadratic equation Continued Fraction Representation 1 e 1 1 1 1 1 2 1 1 1 1 1 4 1 1 1 1 1 6 1 Continued Fraction Representation 1 p 3 1 7 1 15 1 1 1 292 1 1 1 1 1 1 1 2 1 What a cool representation Finite CF Rationals Periodic CF Quadratic Roots And some numbers reveal hidden regularity And there is more Let a1 a2 a3 be a CF Define C1 a1 0 0 0 0 Define C2 a1 a2 0 0 0 Define C3 a1 a2 a3 0 and so on Let a1 a2 a3 be a CF Ck is called the kth convergent of where is the limit of the sequence C1 C2 C3 Define a rational p q to be a best approximator to a real if no rational number of smaller denominator comes closer For any CF representation of each convergent of the CF is a best approximator for Continued Fraction Representation C1 3 C2 22 7 1 C3 333 106 C4 355 113 C5 …
View Full Document
Unlocking...