I want to be able to write down unending
sequences of numbers.
[SOUND].
If I want to give you a sequence of
numbers to analyze, how do I do that?
It's not enough for me just to list off a
finite number of terms.
I somehow have to provide you with all of
the terms at once.
Well, one thing I could do is give you a
formula.
Like a sub N equals n squared.
And this formula would define the sequence
of perfect squares.
If I star with index 1, the sequence
starts 1, 4, 9, 16, 25, and so on.
I can just give you the sequence by giving
you this formula.
Sometimes it can be quite hard to give a
formula for the nth term of the sequence.
We could instead think recursively.
What I mean, is that I could give
you a formula that references previous
terms in the sequence.
For example, we might begin a sequence
with a 0 term that I'll define to
be equal to 0, and an F sub 1 term, which
I'll define to be equal to 1.
And then I'll define future terms by
referring to past terms.
So, in this example,
F sub n will be defined as F sub n minus 1
plus F sub n minus 2.
That's just an example.
Let's see how this works.
Let's say, I want to compute F sub 2.
Well how do I do that?
Well, I can use this formula but replace
with n with 2.
And in that case, I get F sub 2 is F sub
two minus 1 plus F sub
2 minus 2.
But F sub 2 minus 1 is F sub 1.
And F sub 2 minus 2 is F sub 0.
And what's F sub 1?
Well, I know these two facts, I know that
F sub 1 is 1.
And I know that F sub 0 is 0.
And consequently F sub 2 is 1.
And we could keep going.
Let's compute F sub 3.
Replacing n with 3, I find that F sub 3 is
F
sub 3 minus 1 plus F sub 3 minus 2.
But F sub
3 minus 1 is F sub 2.
And F sub 3 minus 2 is F sub 1.
Now I just computed F sub 2 a minute ago,
F sub 2 is 1.
So that tells me that F sub 3, which is F
sub
2 plus F sub 1, is 1 plus F sub 1 is 1,
and 1 plus 1 is 2.
So F sub 3 is 2.
And we can keep going.
Well, let's compute F sub 4.
So, if I want to compute F sub 4, I
replace n with 4 and I find that F sub 4
is F sub 4 minus 1 plus F sub
4 minus 2.
4 minus 1 is 3.
And 4 minus 2 is 2.
So F sub 4 is F sub 3 plus F sub 2.
Alright, each term is the sum of the
previous two terms.
Now, what's F sub 3?
Well, I just computed F sub 3 a moment
ago.
F sub 3 was F sub 2 plus F sub 1, which
was 2.
So F sub
3 is 2.
And I computed F sub 2 a couple moments
ago, and I found that it was 1.
So F sub 4 is 3.
We're maybe beginning to see a pattern.
1, 2, 3, but that pattern does not
continue.
Let's check.
F sub 5 is F sub 4 plus F sub 3.
F sub 4,
I just computed was 3, and F sub 3, I
computed a little while ago to be 2.
And 3 plus 2 is 5.
So F sub 5 is 5.
What's F sub 6?
Well, F sub 6 is F sub 5 plus F sub 4.
It just computed F sub 5 and that was 5
and F
sub 4 was 3, and 5 plus 3 is 8.
So F sub 6 is 8.
This sequence has a name.
So this particular example is called the
Fibonacci Sequence.
It starts 0, 1, and then each term is the
sum of the previous two.
So the next term is 1, 0 plus 1, the next
term is 2, the next
term is 3, the next term is 5 The next
term is 8, and so on.
This isn't to say that the only way to
talk
about the Fibonacci sequence is by giving
a recursive formula.
We're going to see later on in this
course, that it's possible
to write down an explicit formula for the
nth Fibonacci number.
But that's not really the main point here.
The, the main point is that,
when you're thinking about sequences or
you
want to provide someone else with a
sequence.
You don't have to give a formula just in
terms of the index.
Your formula for the nth term can do more
than just refer to n.
Indeed, a formula like this one can refer
to previous terms in the sequence.
[NOISE]