Report

Fibonacci Sequences Susan Leggett, Zuzana Zvarova, Sara Campbell Fundamentals of Mathematics Mentor: Professor Foote What Are Fibonacci Sequences? • A series of numbers in which each number is the sum of the two preceding numbers, where by definition the first two numbers are 0 and 1 • The sequence of Fibonacci numbers is defined by the recurrence relation: Fn= Fn-1 + Fn-2 • Though found in many cultures, the sequences were named after Leonard of Pisa, also known as Fibonacci, after he published a book introducing the sequences to the western world 0,1,1,2,3,5,8,13,21,34,55,… Applications • Euclid’s Algorithm • Hilbert’s Tenth Problem • Used in pseudorandom number generators • Computer programming • Music • Conversion factor • Branching of trees and arrangement of fruit/flowers • Bee ancestry code • The Da Vinci Code • Architecture Fibonacci Identities • Come from Combinatorial arguments • F(n) can be interpreted as the number of sequences of 1s and 2s that have a sum of n-1 • F(0) = 0 so that no sum will add to a negative value (empty sum will add to 0) • Summands matters ( 1+2 and 2+1 are different) Popular Identities of Fibonacci Sequences 1. The nth Fibonacci number is the sum of the previous two Fibonacci numbers Fn=Fn-1+ Fn-2 2. The sum of the first n Fibonacci numbers is equal to the n+2nd Fibonacci number minus 1 Σfi=Fn+2-1 3. The sum of the first n-1 Fibonacci numbers, Fj, such that j is odd, is the (2n)th Fibonacci number. The sum of the first n Fibonacci numbers, Fj, such that j is even, is the (2n+1)th Fibonacci number minus 1 ΣF2i=F2n+1-1 4. ΣiFi= nFn+2- Fn+3+2 5. The sum of the squares of the first n Fibonacci numbers is the product of the nth and (n+1)th Fibonacci numbers. ΣFi2=FnFn+1 th 5 Identity Proof by Induction • Inductive Hypothesis: Pn= F2 = FnFn+1 • Base Case: F0 = F1 = 1 • P0 : 12 = 1 x 1 = 1 is true • Assuming the inductive hypothesis for n = k Pk : F2 = FkFk+1 • We are trying to prove: Pk+1 : F2 = Fk+1F(k+1)+1 = Fk+1Fk+2 • (F0)2 + (F1)2 + … + (Fk)2 = FkFk+1 • (F1)2 + … + (Fk)2 + (Fk+1)2 = FkFk+1 + (Fk+1)2 F2 = (Fk + Fk+1) Fk+1 Which gives us Pk+1 : F2 = Fk+1 Fk+2 • Hence by this proof by induction, for all n ≥ 0 we see that Pn is true 5th Identity Geometric Argument • Fibonacci Rectangles • Compute the area of the rectangles • The n-th rectangle is composed of n squares 2 3 1 with side lengths F1, F2, … Fn which is P n= F 2 • The n-th rectangle has side lengths Fn and Fn+1 which is Pn+1 = F2 = Fn+2 Fn+1 • Setting these expressions equal provides another proof 1 8 5 Divisibility Property • Every kth number of the sequence is a multiple of for example every 3rd number of the Fibonacci sequence is even • Thus the Fibonacci sequence is an example of a divisibility sequence • Satisfies the strong divisibility sequence gcd( , ) = gcd(,) Right Triangles • Starting with 5, every second 5x5 Fibonacci number is the length of the hypotenuse of a 4x4 right triangle with integer sides • Every second Fibonacci number is the largest number of a Pythagorean triple 3x3 The Golden Ratio • Consists of two quantities, a and b, such that a>b and a b a a b • φ ≈ 1.61803398874989 is the golden ratio, an irrational mathematical constant • This constant is formally represented as • 1 5 2 The Golden Ratio appears in nature, such as leaf patterns, and math- especially geometry and Fibonacci numbers • We have shown the Fibonacci Sequence as a linear recursion formula: Fn=Fn-1+ Fn-2 • The closed form for the nth Fibonacci number is related to the Golden Ratio as follows: (1 ) n Fn 5 n This closed-form expression is known as Binet’s formula Golden Ratio and Fibonacci Numbers • Proof is by induction, given 1 5 and Fn=Fn-1+ Fn-2 2 (1 ) n • Fn Want to prove Binet’s Formula • Assuming that k Fk (1 ) k 5 n for all n is true 5 • Show that Fk+1=Fk+ Fk-1 is true • Proof by Induction is long, but our knowledge of induction is sufficient to understand it: http://fabulousfibonacci.com/portal/index.php?option=com_content&view=articl e&id=22&Itemid=22 Limit of Consecutive Fibonacci Numbers • 8/5 = 1.6 , 13/8 = 1.625 , 21/13 = 1.615 … • Johannes Kepler showed that these ratios converge to the Golden Ratio lim F n 1 n Fn • The proof involves substitution with Binet’s formula lim n F n 1 Fn lim n n 1 n 1 n n Fibonacci Spiral • Created by connecting opposite corners of Fibonacci squares of circular arcs • The Fibonacci spiral and Fibonacci numbers occur in many aspects of nature, from seashells to flower petal arrangements, tree branching patterns, and reproduction in certain species References • Professor Foote • http://en.wikipedia.org/wiki/Golden_ratio#Golden_ratio_conjugate • http://en.wikipedia.org/wiki/Fibonacci_number • http://fabulousfibonacci.com/portal/index.php?option=com_conten t&view=article&id=22&Itemid=22 • http://www.fq.math.ca/Scanned/3-3/harris.pdf Questions? Homework Problem • Calculate the first ten numbers in the Fibonacci Sequence. Do you see a pattern? (Show all work). Important Formula: Fn= Fn-1 + Fn-2