Advanced Algorithms Analysis
and Design
By
Dr. Nazir Ahmad Zafar
Dr Nazir A. Zafar Advanced Algorithms
Lecture No. 6
Fibonacci Sequences
(Natural Models)
Dr Nazir A. Zafar Advanced Algorithms
Today Covered
In this lecture we will cover the following:
• Fibonacci Problem and its Sequence
• Construction of Mathematical Model
• Explicit Formula Computing Fibonacci
Numbers
• Recursive Algorithms
• Generalizations of Rabbits Problem and
Constructing its Mathematical Models
• Applications of Fibonacci Sequences
Dr Nazir A. Zafar Advanced Algorithms
Fibonacci Sequence
• By studying Fibonacci numbers and constructing
Fibonacci sequence we can imagine how
mathematics is connected to apparently unrelated
things in this universe.
• Even though these numbers were introduced in
1202 in Fibonacci’s book Liber abaci, but these
numbers and sequence are still fascinating and
mysterious to people of today.
• Fibonacci, who was born Leonardo da Pisa gave a
problem in his book whose solution was the
Fibonacci sequence as we will discuss it today.
Dr Nazir A. Zafar Advanced Algorithms
Fibonacci’s Problem
Statement:
• Start with a pair of rabbits, one male and one female, born
on January 1.
• Assume that all months are of equal length and that
rabbits begin to produce two months after their own birth.
• After reaching age of two months, each pair produces
another mixed pair, one male and one female, and then
another mixed pair each month, and no rabbit dies.
How many pairs of rabbits will there be after one year?
Answer: The Fibonacci Sequence!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical
Model
F0 = 0
F1 = 1 end of month 1
end of month 2
F2 = 1
end of month 3
F3 = 2
F4 = 3
end of month 4
end of month 5
F5 = 5
end of month 6
F6 = 8
end of month 7
F7 = 13 end of month 12
... ... ...
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical Model
• Total pairs at level k = Total pairs at level k-1 + Total
pairs born at level k (1)
• Since
Total pairs born at level k = Total pairs at level k-2 (2)
• Hence by equation (1) and (2)
Total pairs at level k = Total pairs at level k-1 + Total
pairs at level k-2
• Now let us denote
Fk = Total pairs at level k
• Now our recursive mathematical model will become
Fk = Fk-1 + Fk-2
Dr Nazir A. Zafar Advanced Algorithms
Computing Values using Mathematical Model
Since Fk = Fk-1 + Fk-2 F0 = 0, F1= 1
• F2 = F 1 + F 0= 1 + 0 = 1
• F3 = F 2 + F 1= 1 + 1 = 2
• F4 = F 3 + F 2= 2 + 1 = 3
• F5 = F 4 + F 3= 3 + 2 = 5
• F6 = F 5 + F 4= 5 + 3 = 8
• F7 = F6 + F5= 8 + 5 = 13
• F8 = F7 + F6= 13 + 8 = 21
• F9 = F8 + F7= 21 + 13 = 34
• F10 = F9 + F8= 34 + 21 = 55
• F11 = F10 + F9= 55 + 34 = 89
• F12 = F11 + F10= 89 + 55 = 144 . . .
Dr Nazir A. Zafar Advanced Algorithms
Explicit Formula Computing
Theorem: Fibonacci Numbers
The fibonacci sequence F0,F1, F2,…. Satisfies
the recurrence relation
Fk Fk 1 Fk 2 k 2
with initial condition F0 F1 1
Find the explicit formula for this sequence.
Solution:
The given fibonacci sequence
Fk Fk 1 Fk 2
Let tk is solution to this, then characteristic equation
t 2 t 1 0
Dr Nazir A. Zafar Advanced Algorithms
Fibonacci Sequence
1 1 4
t
2
1 5 1 5
t1 , t2
2 2
For some real C and D fibonacci sequence satisfies the relation
n n
1 5 1 5
Fn C D
n 0
2 2
n 0
0 0
1 5 1 5
F0 C D
2
2
F0 C D
C D 0 1 F0 0
Dr Nazir A. Zafar Advanced Algorithms
Fibonacci Sequence
Now n 1
1 5 1 5
F1 C D
2 2
1 5 1 5
C D 1 2 F1 1
2 2
Solving 1and 2 simultaneously we get
1 1
C , D
5 5
Hence
n n
1 1 5 1 1 5
Fn
5 2 5 2 5
Dr Nazir A. Zafar Advanced Algorithms
Fibonacci Sequence
After simplifying we get
n n
1 1 5 1 1 5
Fn
5 2 5 2
which is called the explicit formula for the
Fibonacci sequence recurrence relation.
1 5 1 5
Let
and then
2 2
1 n 1 n
Fn
5 5
Dr Nazir A. Zafar Advanced Algorithms
Verification of the Explicit
Example: Compute F Formula 3
1 n 1 n 1 5 1 5
Since Fn where
and then
2
5 5 2
3 3
1 1 5 1 1 5
F3
5 2 5 2
1 1 3.12. 5 3.1.5 5 5 1 1 3.12. 5 3.1.5 5 5
Now, F3
5 8 5 8
F3
1
8. 5
1 3.1. 5 3.1.5 5 5
1
8. 5
1 3.1. 5 3.1.5 5 5
F3
1
8. 5
1 3.1. 5 3.1.5 5 5 1 3.1. 5 3.1.5 5 5 2
Dr Nazir A. Zafar Advanced Algorithms
Recursive Algorithm Computing Fibonacci Numbers
Fibo-R(n)
if n = 0
then 0
Terminating conditions
if n = 1
then 1
else Fibo-R(n-1) + Fibo-R(n-2) Recursive calls
Dr Nazir A. Zafar Advanced Algorithms
Running Time of Recursive Fibonacci Algorithm
• Least Cost: To find an asymptotic bound of computational
cost of this algorithm, we can use a simple trick to solve this
recurrence containing big oh expressions
• Simply drop the big O from the recurrence, solve the
recurrence, and put the O back. Our recurrence
O(1) if n 2
T (n)
T (n 1) T (n 2) n 2
will be refined to
1 if n 2
T (n)
T (n 1) T (n 2) n 2
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical
Model
F0 = 0
F1 = 1 end of month 1
end of month 2
F2 = 1
end of month 3
F3 = 2
F4 = 3
end of month 4
end of month 5
F5 = 5
end of month 6
F6 = 8
end of month 7
F7 = 13 end of month 12
... ... ...
Dr Nazir A. Zafar Advanced Algorithms
Running Time of Recursive Fibonacci Algorithm
• Guess that Fn+1 is the least cost to solve this
recurrence. Why this guess?
n 0, T(n) Fn+1
then Fn+1 will be minimum cost for this recurrence
• We prove it by mathematical induction
Base Case
There are two base cases
For n = 0, T(0) = 1 and F1 = 1, hence T(0) F1
For n = 1, T(1) = 1 and F2 = 1, hence T(1) F2
Dr Nazir A. Zafar Advanced Algorithms
Running Time of Recursive Fibonacci Algorithm
• Inductive Hypothesis
Let us suppose that statement is true some k 1
T(k) Fk+1 , for k =0, 1, 2,. . . and k 1
• Now we show that statement is true for k + 1
• Now, T(k + 1) = T(k) + T(k -1) By definition on T(n)
T(k + 1) = T(k) + T(k -1) Fk+1 + Fk = Fk+2 Assumption
T(k + 1) Fk+2
• Hence the statement is true for k + 1.
• We can now say with certainty that running time of
this recursive Fibonacci algorithm is at least (Fn+1).
Dr Nazir A. Zafar Advanced Algorithms
Running Time of Recursive Fibonacci Algorithm
• Now we have proved that
T(n) Fn+1 , n 0 (1)
• We already proved in solution to recursive relation that
1 n 1 n 1 5 1 5
Fn
where
and (2)
5 5 2 2
It can be easily verified that Fn n/5 (3/2)n
From the equations (1) and (2), T(n) Fn+1 Fn (3/2)n
Hence we can conclude that r unning time of our recursive
Fibonacci Algorithm is:
T(n) = (3/2)n
Dr Nazir A. Zafar Advanced Algorithms
Golden Ratio
• W say that two quantities, x and y, (x < y), are in
the golden ratio if the ratio between the sum, x + y,
of these quantities and the larger one, y, is the
same as the ratio between the larger one, y, and
the smaller one x.
x y y
1.62
y x
• Mathematicians have studied the golden ratio
because of its unique and interesting properties.
Dr Nazir A. Zafar Advanced Algorithms
Golden Ratio
1 5
1.62
2
x 1 0.62,
1
y 1
of course x y and
xy y 1 1
i.e.
y x 1 1
2
1 0
Dr Nazir A. Zafar Advanced Algorithms
Drawback in Recursive Algorithms
Recursion Tree
F(n)
F(n-1) F(n-2)
F(n-2) F(n-3) F(n-3) F(n-4)
F(0) F(1) F(1) F(0)
Dr Nazir A. Zafar Advanced Algorithms
Generalization of Rabbits
Statement: Problem
• Start with a pair of rabbits, one male and one female, born
on January 1.
• Assume that all months are of equal length and that
rabbits begin to produce two months after their own birth.
• After reaching age of two months, each pair produces two
other mixed pairs, two male and two female, and then two
other mixed pair each month, and no rabbit dies.
How many pairs of rabbits will there be after one year?
Answer: Generalization of Fibonacci Sequence!
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, . . .
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical Model
F0 = 0
F1 = 1
F2 = 1
F3 = 3
F4 = 5
F5 = 11
F6 = 21
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical Model
• Total pairs at level k =
Total pairs at level k-1 + Total pairs born at level k (1)
• Since
Total pairs born at level k =
2 x Total pairs at level k-2 (2)
• By (1) and (2), Total pairs at level k =
Total pairs at level k-1 + 2 x Total pairs at level k-2
• Now let us denote
Fk = Total pairs at level k
• Our recursive mathematical model:
Fk = Fk-1 + [Link]-2
• General Model (m pairs production): Fk = Fk-1 + [Link]-2
Dr Nazir A. Zafar Advanced Algorithms
Generalization
• Recursive mathematical model
(one pair production)
Fk = Fk-1 + Fk-2
• Recursive mathematical model
(two pairs production)
Fk = Fk-1 + [Link]-2
• Recursive mathematical model
(m pairs production)
Fk = Fk-1 + [Link]-2
Dr Nazir A. Zafar Advanced Algorithms
Computing Values using Mathematical Model
Since Fk = Fk-1 + [Link]-2 F0 = 0, F1 = 1
• F2 = F1 + 2.F0= 1 + 0 = 1
• F3 = F2 + 2.F1= 1 + 2 = 3
• F4 = F3 + 2.F2= 3 + 2 = 5
• F5 = F4 + 2.F3= 5 + 6 = 11
• F6 = F5 + F4= 11 + 10 = 21
• F7 = F6 + F5= 21 + 22 = 43
• F8 = F7 + F6= 43 + 42 = 85
• F9 = F8 + F7= 85 + 86 = 171
• F10 = F9 + F8= 171 + 170 = 341
• F11 = F10 + F9= 341 + 342 = 683
• F12 = F11 + F10= 683 + 682 = 1365 . . .
Dr Nazir A. Zafar Advanced Algorithms
Another Generalization of Rabbits Problem
Statement:
• Start with a different kind of pair of rabbits, one male and
one female, born on January 1.
• Assume all months are of equal length and that rabbits
begin to produce three months after their own birth.
• After reaching age of three months, each pair produces
another mixed pairs, one male and other female, and then
another mixed pair each month, and no rabbit dies.
How many pairs of rabbits will there be after one year?
Answer: Generalization of Fibonacci Sequence!
0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, . . .
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical
Model
F0 = 0
F1 = 1
F2 = 1
F3 = 1
F4 = 2
F5 = 3
F6 = 4
F7 = 6
F8 = 9
F9 = 13
F10 = 19
Dr Nazir A. Zafar Advanced Algorithms
Construction of Mathematical Model
• Total pairs at level k =
Total pairs at level k-1 + Total pairs born at level k (1)
• Since
Total pairs born at level k = Total pairs at level k-3 (2)
• By (1) and (2)
Total pairs at level k =
Total pairs at level k-1 + Total pairs at level k-3
• Now let us denote
Fk = Total pairs at level k
• This time mathematical model: Fk = Fk-1 + Fk-3
Dr Nazir A. Zafar Advanced Algorithms
Computing Values using Mathematical Model
Since Fk = Fk-1 + Fk-3 F0 = 0, F1= F2= 1
• F 3 = F 2 + F 0= 1 + 0 = 1
• F 4 = F 3 + F 1= 1 + 1 = 2
• F 5 = F 4 + F 2= 2 + 1 = 3
• F 6 = F 5 + F 3= 3 + 1 = 4
• F 7 = F 6 + F 4= 4 + 2 = 6
• F 8 = F 7 + F 5= 6 + 3 = 9
• F9 = F8 + F6= 9 + 4 = 13
• F10 = F9 + F7= 13 + 6 = 19
• F11 = F10 + F8= 19 + 9 = 28
• F12 = F11 + F9= 28 + 13 = 41 . . .
Dr Nazir A. Zafar Advanced Algorithms
More Generalization
• Recursive mathematical model
(one pair, production after three months)
Fk = Fk-1 + Fk-3
• Recursive mathematical model
(two pairs, production after three months)
Fk = Fk-1 + [Link]-3
• Recursive mathematical model
(m pairs, production after three months)
Fk = Fk-1 + [Link]-3
• Recursive mathematical model
(m pairs, production after n months)
Fk = Fk-1 + [Link]-n
Dr Nazir A. Zafar Advanced Algorithms
Applications of Fibonacci Sequences
Fibonacci sequences
• Are used in trend analysis
• By some pseudorandom number generators
• The number of petals is a Fibonacci number.
• Many plants show the Fibonacci numbers in the
arrangements of the leaves around the stems.
• Seen in arrangement of seeds on flower heads
• Consecutive Fibonacci numbers give worst case
behavior when used as inputs in Euclid’s algorithm.
• As n approaches infinity, the ratio F(n+1)/F(n)
approaches the golden ratio:
=1.6180339887498948482...
Dr Nazir A. Zafar Advanced Algorithms
Applications of Fibonacci Sequences
Fibonacci sequences
• The Greeks felt that rectangles whose sides are in
the golden ratio are most pleasing
• The Fibonacci number F(n+1) gives the number of
ways for 2 x 1 dominoes to cover a 2 x n
checkerboard.
• Sum of the first n Fibonacci numbers is F(n+2)-1.
• The shallow diagonals of Pascal’s triangle sum to
Fibonacci numbers.
• Except n = 4, if F(n) is prime, then n is prime.
• Equivalently, if n not prime, then F(n) is not prime.
• gcd( F(n), F(m) ) = F( gcd(n, m) )
Dr Nazir A. Zafar Advanced Algorithms