15 251 Great Theoretical Ideas in Computer Science Recurrences Fibonacci Numbers and Continued Fractions Lecture 9 September 23 2008 Happy Autumnal Equinox http apod nasa gov apod ap080922 html Leonardo Fibonacci Leonardo Fibonacci In 1202 Fibonacci proposed a problem about the growth of rabbit populations Rabbit Reproduction Rabbit Reproduction A rabbit lives forever Rabbit Reproduction A rabbit lives forever The population starts as single newborn pair Rabbit Reproduction A rabbit lives forever The population starts as single newborn pair Every month each productive pair begets a new pair which will become productive after 2 months old Rabbit Reproduction A rabbit lives forever The population starts as 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 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 2 3 4 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 2 3 4 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 1 3 4 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 1 2 4 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 1 2 3 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 1 2 3 5 6 7 Rabbit Reproduction A rabbit lives forever The population starts as 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 Rabbit Reproduction A rabbit lives forever The population starts as 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 rabbits 1 1 2 3 5 8 13 Fibonacci Numbers month 1 2 3 4 5 6 7 rabbits 1 1 2 3 5 8 13 Fibonacci Numbers month 1 2 3 4 5 6 7 rabbits 1 1 2 3 5 8 13 Stage 0 Initial Condition or Base Case Fib 1 1 Fib 2 1 Fibonacci Numbers month 1 2 3 4 5 6 7 rabbits 1 1 2 3 5 8 13 Stage 0 Initial Condition or Base Case Fib 1 1 Fib 2 1 Inductive Rule For n 3 Fib n Fibonacci Numbers month 1 2 3 4 5 6 7 rabbits 1 1 2 3 5 8 13 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 Sequences That Sum To n Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n 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 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 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 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 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 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 4 Sequences That Sum To n Let fn 1 be the number of different sequences of 1 s and 2 s that sum to n 4 2 2 2 1 1 1 2 1 1 1 2 1 1 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 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 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 Fibonacci Identities Fibonacci Identities Some …
View Full Document
Unlocking...