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]