WEBVTT mathematics/algebra-2/eaton
00:00:00.000 --> 00:00:01.900
Welcome to Educator.com.
00:00:01.900 --> 00:00:06.300
Today, we are going to be covering recursion and special sequences.
00:00:06.300 --> 00:00:16.200
The Fibonacci sequence is a particular sequence that states that one term, a < font size="-6" > n < /font > , is equal to the previous two terms,
00:00:16.200 --> 00:00:23.500
a < font size="-6" > n - 1 < /font > + a < font size="-6" > n - 2 < /font > --the term that came just before it and the one before that.
00:00:23.500 --> 00:00:28.700
Fibonacci is an Italian mathematician who lived in the 13th century.
00:00:28.700 --> 00:00:37.400
And he actually brought the knowledge of this type of sequence to Europe; and that is why the sequence is called the Fibonacci sequence.
00:00:37.400 --> 00:00:44.100
This type of formula that you see right here is called a recursive formula.
00:00:44.100 --> 00:00:52.300
**Recursive formula** means that the value of a term depends on previous terms.
00:00:52.300 --> 00:00:58.000
In order to use this type of formula, you would have to start out with a couple of values.
00:00:58.000 --> 00:01:05.500
Looking at the Fibonacci sequence, you need to start out with your first term, 1, and your second term,
00:01:05.500 --> 00:01:10.600
which actually is also 1, because if you don't have those two terms, you can't find the next term.
00:01:10.600 --> 00:01:25.900
So, a₃ is going to be equal to the term that came just before it, a < font size="-6" > n - 1 < /font > (and 3 - 1
00:01:25.900 --> 00:01:32.200
is going to give me a₂), and then the term just before that, which (in this case) is actually the first term.
00:01:32.200 --> 00:01:42.000
a₃ = 1 + 1, or 2; a₄...now I am going to add the previous two terms here, 2 and 1, to get 3.
00:01:42.000 --> 00:01:45.900
The previous two terms, 3 and 2, get me 5.
00:01:45.900 --> 00:01:51.400
I can use this to form a sequence; so I take these terms, and I write them as a sequence:
00:01:51.400 --> 00:02:08.100
1, 1, 2, 3, 5, and you could go on very easily: 5 + 3 is 8; and so on.
00:02:08.100 --> 00:02:14.800
This gives you one recursive formula, which will provide a special sequence called the Fibonacci sequence.
00:02:14.800 --> 00:02:23.000
But just to give you an example of a recursive formula, more generally, remember that a recursive formula
00:02:23.000 --> 00:02:28.300
is one in which the value of a term depends upon previous terms.
00:02:28.300 --> 00:02:39.300
I might say, "OK, a < font size="-6" > n < /font > = 4 times the previous term, plus 2 times the term before that."
00:02:39.300 --> 00:02:49.000
So, if I wanted to find a particular term in this series, and I was told the first term is equal to 1 and the second term is equal to 2,
00:02:49.000 --> 00:02:58.200
and I was asked to find the third term--"What is a₃?"--well, a₃ = 4 times the term
00:02:58.200 --> 00:03:08.000
that came just before, which is 2, plus 2 times the term before that, which is equal to 1.
00:03:08.000 --> 00:03:22.800
So here, a₃ = 8 + 2, which is actually going to be 10.
00:03:22.800 --> 00:03:32.200
So, in this case, I was given a formula, a < font size="-6" > n < /font > equals 4 times the previous term, 4 times 2,
00:03:32.200 --> 00:03:49.500
plus 2 times the term before that, giving me that the third term is going to be equal to 10.
00:03:49.500 --> 00:03:58.100
Iteration is the process of composing a function with itself again and again; what does that mean?
00:03:58.100 --> 00:04:02.300
Iteration is something that can be used to generate a sequence recursively.
00:04:02.300 --> 00:04:09.400
So, if we are composing a function with itself again and again, what the next iteration is depends on the previous one.
00:04:09.400 --> 00:04:12.600
And that goes back to what we talked about with recursion.
00:04:12.600 --> 00:04:23.800
Again, you need a starting point, though; so here, we need to start out with a function and a first value that we are going to use with the function.
00:04:23.800 --> 00:04:28.400
And that is x₀, or "x naught."
00:04:28.400 --> 00:04:32.500
The easiest way to understand this is through an example.
00:04:32.500 --> 00:04:43.400
f(x) = 3x - 1; x₀ = 1; so I have been given my function, and I am given this x₀.
00:04:43.400 --> 00:04:58.900
So, I could be asked to find the first iterate; I am going to find f(x₀), which here equals f(1).
00:04:58.900 --> 00:05:09.000
So, as usual, to find the value of a function when you are given what you want x to be, you just substitute 1 for x.
00:05:09.000 --> 00:05:17.800
3 times 1, minus 1, is 3 minus 1, which equals 2.
00:05:17.800 --> 00:05:34.900
So, I found the first iterate; to find the next iterate, I am actually going to take f(f(x₀)), which is f(f(1).
00:05:34.900 --> 00:05:39.900
And we determined that f(1) is 2, so I just find f(2).
00:05:39.900 --> 00:05:48.300
This gives me 3 times 2, minus 1 equals 6, minus 1, which equals 5.
00:05:48.300 --> 00:05:58.900
If I want to find another iterate, then I am going to take f(f(f(x₀))).
00:05:58.900 --> 00:06:18.700
Here, I know that this in here is 5; so I am taking f(5); this is 3(5) - 1 = 15 - 1 = 14.
00:06:18.700 --> 00:06:28.100
And you can continue on like that: if I wanted to find the next term, it would just be f(f(f(f(x₀)))).
00:06:28.100 --> 00:06:36.500
And you go on that way; so again, this is the process of composing a function with itself again and again and again.
00:06:36.500 --> 00:06:42.800
I could use these numbers to form a sequence; so I have generated a sequence recursively.
00:06:42.800 --> 00:06:49.700
My first term, a₁, is going to be right up here; it equals 1.
00:06:49.700 --> 00:07:01.200
My second term is going to be 2; my third term is 5; and then, my fourth term is going to be 14.
00:07:01.200 --> 00:07:09.000
And I could write this out as a sequence: 1, 2, 5, 14.
00:07:09.000 --> 00:07:15.400
In the first example, I am asked to find the first 5 terms; and I am given that the first term is 3.
00:07:15.400 --> 00:07:28.200
And when I look at this, this is a recursive formula, because the term that I am looking for depends on the term before it.
00:07:28.200 --> 00:07:35.900
So, if I am looking for a < font size="-6" > n + 1 < /font > , it is going to be equal to 2 times the previous term, minus 3.
00:07:35.900 --> 00:07:37.900
And I need to find the first 5 terms.
00:07:37.900 --> 00:07:44.500
Well, the first term is given (the first term is 3); and I need to find a₂.
00:07:44.500 --> 00:08:01.100
a₂ is going to equal 2, times the previous term; so, given whatever n + 1 is, I am going to take away 1 from that and get the previous term.
00:08:01.100 --> 00:08:09.500
So, that is going to give me 2 times 3 minus 3, equals 6 - 3, which equals 3.
00:08:09.500 --> 00:08:13.400
I found the second term; I need to find the third term.
00:08:13.400 --> 00:08:19.300
So, I am going to take 2 times the previous term (the value of that is 3), minus 3.
00:08:19.300 --> 00:08:23.300
You are starting to see a pattern here: again, we have 3.
00:08:23.300 --> 00:08:28.000
Well, I know what is going to happen if I put 3 back into this formula, but I will go ahead and do it anyway.
00:08:28.000 --> 00:08:40.800
2 times 3, minus 6, equals 6 - 3, is 3; I have one more term to find...again, 2 times 3, minus 3, equals 6 - 3, equals 3.
00:08:40.800 --> 00:08:46.100
So, this is actually a sequence where this formula generates the same value over and over and over.
00:08:46.100 --> 00:08:52.100
So, I am just going to end up with a sequence that looks like this; and that is actually going to go on forever.
00:08:52.100 --> 00:09:03.000
This is kind of an interesting formula where we ended up with the same value over and over and over in this sequence.
00:09:03.000 --> 00:09:09.100
Example 2: this time we are going to work with iterates--we are asked to find the first three iterates of this function.
00:09:09.100 --> 00:09:15.600
And the function is f(x) = 4x - 7, and x₀ = 3.
00:09:15.600 --> 00:09:27.000
To find the first iterate, I am going to go ahead and find f(x₀, which equals 4.
00:09:27.000 --> 00:09:28.800
And then, I am going to insert 3 here.
00:09:28.800 --> 00:09:34.900
Actually, just to clarify: this is equal to f(3), because x₀ is 3.
00:09:34.900 --> 00:09:41.900
So, we are going to write this as 4(3) - 7 = 12 - 7; that equals 5.
00:09:41.900 --> 00:09:52.600
That is the first iterate; the second iterate is going to be f(f(x₀)), which, in this case, is going to be f(5).
00:09:52.600 --> 00:10:00.000
That equals 4(5) - 7; that is going to give me 20 - 7, which is 13.
00:10:00.000 --> 00:10:15.600
Next, f(f(f(x₀))): I know that this, in here, is 13, so I just take f(13) = 4(13) - 7.
00:10:15.600 --> 00:10:38.700
4 times 13 is 52, minus 7 gives me 45; so I found the first three iterates, and those are 5, 13, and 45.
00:10:38.700 --> 00:10:45.200
Example 3: Find the first five terms--they give me the first term; they give me the second term;
00:10:45.200 --> 00:10:52.700
and they give me a formula that is a recursive formula, because it depends on the previous two terms.
00:10:52.700 --> 00:11:00.200
So, a < font size="-6" > n < /font > = 2(a < font size="-6" > n - 1 < /font > ) + 3(a < font size="-6" > n - 2 < /font > ).
00:11:00.200 --> 00:11:12.600
I need to find the first five terms: the first term is given; the second term is given; I just need to find a₃, a₄, and a₅.
00:11:12.600 --> 00:11:21.700
Let's start with a₃: a₃ is going to equal 2 times the term that came just before,
00:11:21.700 --> 00:11:27.800
or a₂, plus 3 times the term before that, which is a₁.
00:11:27.800 --> 00:11:39.100
This is going to be equal to 2 times 3, plus 3 times 2, equals 6 + 6; that is going to give me 12.
00:11:39.100 --> 00:11:48.000
So, a₃ is 12; a₄ is going to be equal to 2 times a₃, plus 3 times a₂,
00:11:48.000 --> 00:11:57.400
which equals 2 times...a₃ is 12, plus 3 times a₂, which is 3.
00:11:57.400 --> 00:12:09.900
Of course, 2 times 12 is 24, plus 3 times 3 (is 9)...24 + 9 is 33: a₄ is 33.
00:12:09.900 --> 00:12:21.700
a₅ is equal to 2 times a₄, plus 3 times a₃; this is going to be equal to 2 times 33, plus 3 times 12.
00:12:21.700 --> 00:12:31.600
That is going to give me 66, plus 3 times 12 (is 36), and that adds up to 102.
00:12:31.600 --> 00:12:42.800
So, I found the first 5 terms; I was actually given these 2; and then, I used a recursive formula to find the third, fourth, and fifth terms.
00:12:42.800 --> 00:12:52.000
Find the first three iterates: f(x) = x² + 3x - 4; and then, x₀, or "x naught," is equal to 1.
00:12:52.000 --> 00:13:10.100
The first iterate will be f(x₀), which equals f(1); that gives me 1² + 3(1) - 4, equals 1 - 3 - 4.
00:13:10.100 --> 00:13:25.600
So, I have, let me see...actually, that is plus right here...so that is 1² + 3 - 4, so 1 + 3 - 4; that is 4 - 4; the first iterate is 0.
00:13:25.600 --> 00:13:36.800
The next iterate: f(f(x₀)): this is going to be equal to...since f(x₀) is 0, it is just f(0).
00:13:36.800 --> 00:13:49.200
0² + 3(0) - 4 is 0 + 0 - 4; so that is going to give me -4.
00:13:49.200 --> 00:14:07.500
Next, I want f(f(f(x₀))); this is going to be equal to f(-4) = (-4)² + 3(-4) - 4.
00:14:07.500 --> 00:14:29.200
This equals 16 - 12 - 4; well, -12 and -4 are -16, so this is 16 - 16 = 0; so the first three iterates are 0, -4, and 0.
00:14:29.200 --> 00:14:34.000
That concludes this lesson of Educator.com; thanks for visiting, and see you soon!