Transcript 1 - Montgomery College

Fibonacci’s rabbits
Fibonacci posed the following problem:
A mature pair of rabbits can give birth to a new
pair of baby rabbits every month.
Juvenile rabbits require 1 month to mature, and
then they too start breeding.
If you start with 1 pair of juvenile rabbits, how
many pairs of rabbits will you have after 3
months? 6 months? 1 year? Is there a pattern
that will let us determine how many rabbits we
will have after N months, for any N ?
Initially:
1 pair of juvenile rabbits
After 1 month
The pair of rabbits are now mature
After 2 months
The original pair of rabbits are (still) mature, and
there is now a new pair of juvenile offspring.
After 3 months….
And 4...
And 5...
And 6...
And 7...
During this
there are this many
number month
pairs of young rabbits
and
this many pairs
of mature rabbits
total
During this
there are this many
number month
pairs of young rabbits
1
1
and
this many pairs
total
of mature rabbits
1
During this
there are this many
number month
pairs of young rabbits
1
2
and
this many pairs
total
of mature rabbits
1
1
1
Any rabbits that were around initially are mature
after 1 month.
1
During this
there are this many
number month
pairs of young rabbits
1
this many pairs
1
total
of mature rabbits
1
2
3
and
1
1
1
1
2
Any rabbits that were around after 1 month are mature
after 2 months. Any rabbits that were mature after 1
month give birth to offspring in the 2nd month.
During this
there are this many
number month
pairs of young rabbits
1
and
this many pairs
of mature rabbits
1
2
total
1
1
1
3
1
1
2
4
1
2
3
Any rabbits that were around after 2 months are mature
after 3 months. Any rabbits that were mature after 2
month give birth to offspring in the 3rd month.
During this
there are this many
number month
pairs of young rabbits
1
and
this many pairs
of mature rabbits
1
2
total
1
1
1
3
1
1
2
4
1
2
3
5
2
3
5
During this
there are this many
number month
pairs of young rabbits
1
and
this many pairs
of mature rabbits
1
2
total
1
1
1
3
1
1
2
4
1
2
3
5
2
3
5
6
3
5
8
During this
there are this many
number month
pairs of young rabbits
1
and
this many pairs
of mature rabbits
1
2
total
1
1
1
3
1
1
2
4
1
2
3
5
2
3
5
6
3
5
8
7
5
8
13
During this
there are this many
number month
pairs of young rabbits
1
and
this many pairs
of mature rabbits
1
2
total
1
1
1
3
1
1
2
4
1
2
3
5
2
3
5
6
3
5
8
7
5
8
13
8
8
13
21
General Pattern:
In any given month, the total number of rabbits =
number of mature rabbits + number of juvenile rabbits.
General Pattern:
In any given month, the total number of rabbits =
number of mature rabbits + number of juvenile rabbits.
But the number of mature rabbits = the total number of rabbits
from the previous month,
and
the number of juvenile rabbits = the number of mature rabbits
from the previous month, which is the same as the total
number of rabbits from 2 months prior.
General Pattern:
In any given month, the total number of rabbits =
number of mature rabbits + number of juvenile rabbits.
But the number of mature rabbits = the total number of rabbits
from the previous month, and the number of juvenile rabbits =
the number of mature rabbits from the previous month, which
is the same as the total number of rabbits from 2 months prior.
Conclusion:
The number of rabbits in any month can be found by
adding the number of rabbits one month earlier to the
number of rabbits 2 months earlier.
General Pattern:
Let fn represent the total number of rabbits after n months.
Then, we have the formula
fn
=
fn-1
number of rabbits after
number after
n months
n-1 months
+
+
fn-2
number after
n-2 months
After this many months…
there are this many pairs of rabbits
1
1
2
1
3
2
4
3
5
5
6
8
7
13
8
21
General formula…
fn = fn-1 + fn-2
After this many months…
there are this many pairs of rabbits
1
1
2
1
3
2
4
3
5
5
6
8
7
13
8
21
General formula…
fn = fn-1 + fn-2 with initial conditions f1 = f2 =1.
The Fibonacci sequence:
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
The Fibonacci sequence:
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
What is the next Fibonacci number?
The Fibonacci sequence:
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
34+55=89, so 89 comes next.
The Fibonacci sequence:
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
We now know how many rabbits there will be
after 11 months – 1 more month and we
have an answer to Fibonacci’s original
question.
The Fibonacci sequence:
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
55+89=144, so there are 144 pairs of rabbits
after 1 year.
Recall that a sequence is recursively defined
if, as in Fibonacci’s example, the rule for
finding the next number is based on the
numbers already found.
Recursively defined sequences are often easy
to work with, but they do suffer from one
serious drawback:
Recursively defined sequences are often easy
to work with, but they do suffer from one
serious drawback:
What is the 50th Fibonacci number?
What is the 50th Fibonacci number?
To answer that we need to know the 48th and
49th Fibonacci numbers.
But to find these we need to know the 47th
Fibonacci number, and so on…
There is no way of finding the 50th without
first finding each of the first 49.
There is also an explicit definition for this
sequence - an explicit formula, or algebraic
rule, which tells you how to compute the
any number directly.
The Fibonacci sequence, explicit
formula:
This is known as Binet’s formula:
N
N

 1  1 5  1 5  
fN  
  2    2  
 5  
 
 
 1 5 


 2 
The number
is important enough that it is
given a symbol, Φ, the Greek letter Phi.
A large portion of this chapter will deal with
properties of Φ.
Note that using Binet’s formula and
replacing “N” with 50, we can find
the 50th Fibonacci number
N
N

 1  1 5  1 5  
fN  
  2    2  
 5  
 
 
= 12,586,269,025