This preview shows page 1-2-3-4-5-6-7-8-9-62-63-64-65-66-67-68-69-124-125-126-127-128-129-130-131-132 out of 132 pages.
15-251Great Theoretical Ideas in Computer ScienceRecurrences, Fibonacci Numbers and Continued FractionsLecture 9, September 23, 2008Happy Autumnal Equinoxhttp://apod.nasa.gov/apod/ap080922.htmlLeonardo FibonacciLeonardo FibonacciIn 1202, Fibonacci proposed a problem about the growth of rabbit populationsRabbit ReproductionRabbit ReproductionA rabbit lives foreverRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth monthmonth1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth monthmonth1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1 2month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1 32month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1 3 52month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1 3 52 8month1234567rabbitsRabbit ReproductionA rabbit lives foreverThe population starts as single newborn pairEvery month, each productive pair begets a new pair which will become productive after 2 months oldFn= # of rabbit pairs at the beginning of the nth month1 1 3 52 8 13Fibonacci Numbersmonth1234567rabbits1 1 3 52 8 13Fibonacci NumbersStage 0, Initial Condition, or Base Case:Fib(1) = 1; Fib (2) = 1month1234567rabbits1 1 3 52 8 13Fibonacci NumbersStage 0, Initial Condition, or Base Case:Fib(1) = 1; Fib (2) = 1Inductive Rule:For n>3, Fib(n) =month1234567rabbits1 1 3 52 8 13Fibonacci NumbersStage 0, Initial Condition, or Base Case:Fib(1) = 1; Fib (2) = 1Inductive Rule:For n>3, Fib(n) =Fib(n-1) + Fib(n-2)month1234567rabbits1 1 3 52 8 13Sequences That Sum To nSequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1 0 = the empty sumSequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1 0 = the empty sumf2 = 1Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1 0 = the empty sumf2 = 1 1 = 1Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1 0 = the empty sumf2 = 1 1 = 1f3 = 2Sequences That Sum To n2 = 1 + 1 2Let fn+1 be the number of different sequences of 1’s and 2’s that sum to n.f1 = 1 0 = the empty sumf2 = 1 1 = 1f3 = 2Sequences That Sum To nLet 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 + 1Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.4 =Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.fn+1 = fn + fn-1Sequences That Sum To nLet 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 2# of sequences beginning with a 1Sequences That Sum To nLet fn+1 be the number of different sequences of 1’s and 2’s that sum to n.Fibonacci Numbers Againfn+1 = fn + fn-1f1 = 1 f2 = 1Let fn+1 be the number of different sequences of 1’s and 2’s that sum to n.Visual Representation: TilingLet fn+1 be the number of different ways to tile a 1 × n strip with squares and dominoes.1 way to tile a strip of length 01 way to tile a strip of length 1:2 ways to tile a strip of length 2:Visual Representation: Tilingfn+1 = fn + fn-1fn+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 IdentitiesFibonacci IdentitiesSome examples:Fibonacci IdentitiesSome examples:Fibonacci IdentitiesSome examples:F2n = F1 + F3 + F5 + … + F2n-1Fibonacci IdentitiesSome examples:F2n = F1 + F3 + F5 + … + F2n-1Fibonacci IdentitiesSome examples:F2n = F1 + F3 + F5 + … + F2n-1Fm+n+1 = Fm+1 Fn+1 + Fm FnFibonacci IdentitiesSome examples:F2n = F1 + F3 + F5 + … + F2n-1Fm+n+1 = Fm+1 Fn+1 + Fm FnFibonacci IdentitiesSome examples:F2n = F1 + F3 + F5 + … + F2n-1Fm+n+1 = Fm+1 Fn+1 + Fm Fn(Fn)2 = Fn-1 Fn+1 + (-1)nFm+n+1 = Fm+1 Fn+1 + Fm FnFm+n+1 = Fm+1 Fn+1 + Fm FnmnFm+n+1 = Fm+1 Fn+1 + Fm Fnmnm-1n-1(Fn)2 = Fn-1 Fn+1 + (-1)n(Fn)2 = Fn-1 Fn+1 + (-1)nn-1Fn tilings of a strip of length n-1(Fn)2 = Fn-1 Fn+1 + (-1)nn(Fn)2 tilings of two strips of size n-1(Fn)2 = Fn-1 Fn+1 + (-1)nnDraw a vertical “fault
View Full Document