- Date:07 Jul 2020
- Views:24
- Downloads:0
- Size:1.87 MB

Transcription:

Great Theoretical Ideasin Computer Science Recurrences Fibonacci Numbersand Continued FractionsLecture 9 September 24 2009.

Leonardo FibonacciIn 1202 Fibonacci proposed a problemabout the growth of rabbit populations Rabbit ReproductionA rabbit lives forever.

The population starts as single newborn pairEvery month each productive pairbegets a new pair which will becomeproductive after 2 months oldFn of rabbit pairs at the beginning.

of the nth monthmonth 1 2 3 4 5 6 7rabbits 1 1 2 3 5 8 13 Fibonacci Numbersmonth 1 2 3 4 5 6 7.

rabbits 1 1 2 3 5 8 13Stage 0 Initial Condition or Base Case Fib 1 1 Fib 2 1Inductive Rule For n 3 Fib n Fib n 1 Fib n 2 .

Sequences That Sum To nLet fn 1 be the number of differentsequences of 1 s and 2 s that sum to n f1 10 the empty sumf2 1 1 1.

f3 2 2 1 1 Sequences That Sum To nLet fn 1 be the number of differentsequences of 1 s and 2 s that sum to n 1 1 1 1.

Sequences That Sum To nLet fn 1 be the number of differentsequences of 1 s and 2 s that sum to n fn 1 fn fn 1sequences sequences.

beginning beginningwith a 1 with a 2 Fibonacci Numbers AgainLet fn 1 be the number of differentsequences of 1 s and 2 s that sum to n .

fn 1 fn fn 1f1 1 f2 1 Visual Representation TilingLet fn 1 be the number of differentways to tile a 1 n strip with.

squares and dominoes Visual Representation Tiling1 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 .

fn 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 Fibonacci Identities.

Some examples F2n F1 F3 F5 F2n 1Fm n 1 Fm 1 Fn 1 Fm Fn Fn 2 Fn 1 Fn 1 1 n Fm n 1 Fm 1 Fn 1 F m Fn.

Fn 2 Fn 1 Fn 1 1 nFn tilings of a strip of length n 1 Fn 2 Fn 1 Fn 1 1 n Fn 2 tilings of two strips of size n 1 Fn 2 Fn 1 Fn 1 1 n.

Draw a vertical faultline at the rightmostposition n possiblewithout cutting any Fn 2 Fn 1 Fn 1 1 n.

Swap the tails at thefault line to map to atiling of 2 n 1 s to atiling of an n 2 and an Fn 2 Fn 1 Fn 1 1 n 1.

Sneezwort Achilleaptarmica Each time the plant starts a new shootit takes two months before it is strongenough to support branching Counting Petals.

5 petals buttercup wild rose larkspur columbine aquilegia 8 petals delphiniums13 petals ragwort corn marigold cineraria .

some daisies21 petals aster black eyed susan 34 petals plantain pyrethrum55 89 petals michaelmas daisies theasteraceae family .

The Fibonacci Quarterly Definition of Euclid Ratio obtained when you divide a linesegment into two unequal parts such thatthe ratio of the whole to the larger part is.

the same as the ratio of the larger to the A B C 1 0 Golden ratio supposed to ariseParthenon Athens 400 B C The great pyramid at Gizeh.

circumstantialRatio of a person s height evidence to the height of his her navel Expanding Recursively Expanding Recursively.

Continued FractionRepresentation A Simple Continued Fraction Is AnyExpression Of The Form where a b c are whole numbers .

A Continued Fraction can have afinite or infinite number of terms We also denote this fraction by a b c d e f A Finite Continued FractionDenoted by 2 3 4 2 0 0 0 .

An Infinite Continued FractionDenoted by 1 2 2 2 Recursively Defined Form For CF Continued fraction representation ofa standard fraction.

e g 67 29 2 with remainder 9 29 2 1 29 9 Ancient Greek Representation Continued Fraction Representation Ancient Greek Representation .

Continued Fraction Representation 1 1 1 1 0 0 0 Ancient Greek Representation Continued Fraction Representation Ancient Greek Representation .

Continued Fraction Representation 1 1 1 1 1 0 0 0 Ancient Greek Representation Continued Fraction Representation 1 1 1 1 1 1 0 0 0 .

A Pattern Let r1 1 0 0 0 1r2 1 1 0 0 0 2 1r3 1 1 1 0 0 0 3 2r4 1 1 1 1 0 0 0 5 3.

and so on rn Fib n 1 Fib n 1 1 2 3 5 8 13 21 34 55 5 3 1 666 13 8 1 625.

21 13 1 6153846 34 21 1 61904 1 6180339887498948482045 Pineapple whorlsChurch and Turing were both.

interested in the number ofwhorls in each ring of theThe ratio of consecutive ringlengths approaches theGolden Ratio .

Proposition Any finite continuedfraction evaluates to aAny rational has a finitecontinued fraction.

representation Finite CFs Rationals Then what doinfinite continued fractionsrepresent .

An infinite continued fraction Quadratic Equations X2 3x 1 0 X2 3X 1 X 3 1 X.

X 3 1 X 3 1 3 1 X A Periodic CF Theorem Any solution to a quadraticequation has a periodic.

continued fraction Any periodic continuedfraction is the solution of aquadratic equation try to prove this .

So they express morethan just the rationals What about thosenon recurring infinitecontinued fractions .

Non periodic CFs What is the pattern No one knows What a cool representation Finite CF Rationals.

Periodic CF Quadratic rootsAnd some numbers revealhidden regularity More good news ConvergentsLet a1 a2 a3 be a CF .

Define C1 a1 0 0 0 0 C2 a1 a2 0 0 0 C3 a1 a2 a3 0 0 and so on Ck is called the k th convergent of is the limit of the sequence C1 C2 C3 .

Best Approximator Theorem A rational p q is the best approximatorto a real if no rational number ofdenominator smaller than q comescloser to .

BEST APPROXIMATOR THEOREM Given any CF representation of each convergent of the CF is abest approximator for Best Approximators of .

C3 333 106C4 355 113C5 103993 33102C6 104348 33215 Continued Fraction.

Representation Continued FractionRepresentation Remember 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 1 1 2 3 5 8 13 21 34 55 2 1 2 3 2 1 5.

5 3 1 666 8 5 1 6 13 8 1 625 21 13 1 6153846 34 21 1 61904 .

1 6180339887498948482045 As we ve seen Going the Other Way Recurrences and generatingGolden ratio.

Continued fractionsConvergentsHere s WhatYou Need to Closed form for Fibonaccis.

* Recurrences and generating functions Golden ratio Continued fractions Convergents Closed form for Fibonaccis Hereâ€™s What You Need to Knowâ€¦ Recursively Defined Form For CF Continued fraction representation of a standard fraction e.g., 67/29 = 2 with remainder 9/29 = 2 + 1/ (29/9) Ancient Greek Representation: Continued Fraction ...

Recent Views:

- Parent meeting for 9th 11th grades
- Progress in n 2 field theory
- Aashto rac value of research task force report
- Medical direction caa med com
- Colonial north america weebly
- Marxist theories of ir university of nottingham
- Contemporary business writing across the curriculum two
- Chapter 2 control structures
- Comparing populisms finland and hungary
- Program ppm pengabian kepada masyarakat