Example 13.2– Fibonacci Numbers Get Big Fast

Example – Fibonacci Numbers Get Big Fast

1.60M

Section 13.1 Math Discovery

1. Chapter 1: The mathematics of elections

Chapter 13:Fibonacci
Numbers and the
Golden Ratio
Section 13.1: Fibonacci
Numbers
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 1

2. Fibonacci Sequence

• Infinite list form:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
The numbers in the Fibonacci sequence are called the Fibonacci
numbers. (The conventional notation is to use FN to describe the
Nth Fibonacci number and to start the count at F1, so we write F1
= 1, F2 = 1, F3 = 2, F4 = 3, etc.)
• Recursive formula:
FN = FN-1 + FN-2; F1 = 1 and F2 = 1.
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 2

3. Example 13.2– Fibonacci Numbers Get Big Fast

Suppose you were given the following choice: You can have $100
billion or a sum equivalent to F100 pennies. Which one would you
choose? Surely, this is a no brainer—how could you pass on the
$100 billion? (By the way, that much money would make you
considerably richer than Bill Gates.) But before you make a rash
decision, let’s see if we can figure out the dollar value of the
second option. To do so, we need to compute the 100th Fibonacci
number F100.
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 3

4. Example – Fibonacci Numbers Get Big Fast

How could one find the value of F100? With a little patience (and a
calculator) we could use the recursive formula for the Fibonacci
numbers as a “crank” that we repeatedly turn to ratchet our way up
the Fibonacci sequence: From the seeds F1
and F2 we compute F3, then use F3 and F2 to compute F4, and so
on. If all goes well, after many turns of the crank (we will skip the
details) you will eventually get to
F100 = F99 + F98 = 354,224,848,179,261,915,075
≈ $3,542,248,481,792,619,150
(That’s enough for you to take your $100 billion and give every
man, woman, and child on Earth more that $450 million each!
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 4

5. Fibonacci Sequence: Explicit Formulas

In 1736 Leonhard Euler (the same Euler behind the namesake
theorems in Chapter 5) discovered a formula for the Fibonacci
numbers that does not rely on previous Fibonacci numbers. The
formula was lost and rediscovered 100 years later by French
mathematician and astronomer Jacques Binet, who somehow
ended up getting all the credit, as the formula is now known as
Binet’s formula.
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 5

6. Binet’s Formula (Original Version)

1 5 N 1 5 N
FN
2 2
5
Admittedly, Binet’s original formula is quite complicated and
intimidating, and even with a good calculator you might have
trouble finding an exact value when N is large, but there is a
simplified version of the formula that makes the calculations a bit
easier.
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 6

7. Binet’s Formula (Simplified Version)

1 5
FN
2
N
5
where
means “rounded to the nearest integer.
Binet’s simplified formula is an explicit formula (we don’t have
to know the previous Fibonacci numbers to use it), but it only
makes sense to use it to compute very large Fibonacci numbers
(for smaller numbers you are much better off using the recursive
formula).
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 7

8. Fibonacci Numbers in Nature

One of the major attractions of the Fibonacci numbers is how
often they show up in natural organisms, particularly flowers and
plants that grow as spirals.
• The petal counts of most varieties of daisies are Fibonacci
numbers—most often 3, 5, 8, 13, 21, 34, or 55 (but giant
daisies with 89 petals also exist).
• The bracts of a typical pinecone are arranged in 5, 8, and 13
spiraling rows depending on the direction you count.
• The seeds on a sunflower head are arranged in 21 and 34
spiraling rows.
ALWAYS LEARNING
Copyright © 2022, 2018, 2014 Pearson Education Inc.
Slide 8