Transcript Fibonacci number

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