This right here is a picture of Fibonacci,
one of the most famous mathematicians of all time,
and he was a mathematician in medieval Italy.
And he's most famous for the Fibonacci numbers.
And he didn't discover them.
They were actually discovered several centuries before him
in India, but he popularized them, especially in the West.
And the Fibonacci numbers are super simple.
The first two are defined as 0 and 1.
And every number after that is the sum of the previous two.
So what I'm constructing right here
is really a Fibonacci sequence of numbers.
So the next number in the sequence
is going to be 0 plus 1, which is 1, Then
the next number after that is going to be 1 plus 1,
which is 2.
Then the next number after that 1 plus 2 is 3.
2 plus 3 is 5.
3 plus 5 is 8.
5 plus 8 is 13.
8 plus 13 is 21.
13 plus 21 is 34.
And the Fibonacci numbers, especially once
you start getting into number theories, tons
of fascinating things about them.
But probably the coolest thing about them
is as you add more and more terms to the Fibonacci
sequence, and you take the last two terms
that you've generated, obviously there is no really last two
terms.
You could keep going on forever, get arbitrarily
large Fibonacci numbers.
But say we take these last two terms over here, 21 and 34.
If we take the ratio of these two, 21 over 34,
this is going to be pretty close to the golden ratio.
And I encourage you to look up the golden ratio on Wikipedia
and the internet.
You'll find all sorts of fascinating and mystical things
about the golden ratio.
What's cool about the Fibonacci numbers, or the Fibonacci
sequence, this gives you an approximation
of the golden ratio.
You'll get even a better approximation
if you add another term to our sequence.
So the next term over here, 21 plus 34 is 55.
So the ratio of 34 to 55 is even closer to the golden ratio.
So one way, if you wanted to compute
a really good approximation for the golden ratio,
you could really just get super high Fibonacci numbers
just adding the previous two terms to get the next one.
And you will get a pretty good approximation,
when you take the ratio of the last two terms.
Now that's what the Fibonacci numbers are about,
and now I want to pose a challenge to you.
I want you to write, since we've already
done some examples using factorial,
I want you to write an implementation
of a function that generates the n-th term in the Fibonacci
sequence.
So the function will be like this.
So if I call your function-- Let me make it a lowercase.
Let me just give you some examples.
So if I take your function, and I call Fibonacci--
and you could really implement this in any language you want,
although we've been dealing in Python,
it might be simplest to do it in Python--
if I call fibonacci of 1, what I want this to be
is the first term.
And just to make things clear, and you should always
clarify this, especially in computer science,
because it's not always clear what the first term is.
And I'm going to make it clear right now.
The first term is not going to be this one over here.
I'm going to make it this one over here.
I'm going to call this the 0-th term.
That's the 0-th term, and then that
is going to be the first term.
This is going to be the second term, third term, fourth term,
so on and so forth.
And so Fibonacci of 1, the first term
will be this right over here.
It should return 1.
So Fibonacci of 0 should return 0.
Fibonacci of 3 should return 0, 1, 2, 3.
It should return 2.
Fibonacci of 5 should return 0, 1, 2, 3, 4, 5.
It should actually return 5.
And what I want you to do is write a function
so we could put in any argument over here
and it will return that third term of the Fibonacci sequence.