Algebra 2 Recursion and Special Sequences

Welcome to Educator.com.0000

Today, we are going to be covering recursion and special sequences.0002

The Fibonacci sequence is a particular sequence that states that one term, a_n, is equal to the previous two terms,0006

a_{n - 1} + a_{n - 2}--the term that came just before it and the one before that.0016

Fibonacci is an Italian mathematician who lived in the 13^th century.0023

And he actually brought the knowledge of this type of sequence to Europe; and that is why the sequence is called the Fibonacci sequence.0029

This type of formula that you see right here is called a recursive formula.0037

Recursive formula means that the value of a term depends on previous terms.0044

In order to use this type of formula, you would have to start out with a couple of values.0052

Looking at the Fibonacci sequence, you need to start out with your first term, 1, and your second term,0058

which actually is also 1, because if you don't have those two terms, you can't find the next term.0065

So, a₃ is going to be equal to the term that came just before it, a_{n - 1} (and 3 - 10070

is going to give me a₂), and then the term just before that, which (in this case) is actually the first term.0086

a₃ = 1 + 1, or 2; a₄...now I am going to add the previous two terms here, 2 and 1, to get 3.0092

The previous two terms, 3 and 2, get me 5.0102

I can use this to form a sequence; so I take these terms, and I write them as a sequence:0106

1, 1, 2, 3, 5, and you could go on very easily: 5 + 3 is 8; and so on.0111

This gives you one recursive formula, which will provide a special sequence called the Fibonacci sequence.0128

But just to give you an example of a recursive formula, more generally, remember that a recursive formula0135

is one in which the value of a term depends upon previous terms.0143

I might say, "OK, a_n = 4 times the previous term, plus 2 times the term before that."0148

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,0159

and I was asked to find the third term--"What is a₃?"--well, a₃ = 4 times the term0169

that came just before, which is 2, plus 2 times the term before that, which is equal to 1.0178

So here, a₃ = 8 + 2, which is actually going to be 10.0188

So, in this case, I was given a formula, a_n equals 4 times the previous term, 4 times 2,0203

plus 2 times the term before that, giving me that the third term is going to be equal to 10.0212

Iteration is the process of composing a function with itself again and again; what does that mean?0229

Iteration is something that can be used to generate a sequence recursively.0238

So, if we are composing a function with itself again and again, what the next iteration is depends on the previous one.0242

And that goes back to what we talked about with recursion.0249

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.0252

And that is x₀, or "x naught."0264

The easiest way to understand this is through an example.0268

f(x) = 3x - 1; x₀ = 1; so I have been given my function, and I am given this x₀.0272

So, I could be asked to find the first iterate; I am going to find f(x₀), which here equals f(1).0283

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.0299

3 times 1, minus 1, is 3 minus 1, which equals 2.0309

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).0318

And we determined that f(1) is 2, so I just find f(2).0335

This gives me 3 times 2, minus 1 equals 6, minus 1, which equals 5.0340

If I want to find another iterate, then I am going to take f(f(f(x₀))).0348

Here, I know that this in here is 5; so I am taking f(5); this is 3(5) - 1 = 15 - 1 = 14.0359

And you can continue on like that: if I wanted to find the next term, it would just be f(f(f(f(x₀)))).0379

And you go on that way; so again, this is the process of composing a function with itself again and again and again.0388

I could use these numbers to form a sequence; so I have generated a sequence recursively.0396

My first term, a₁, is going to be right up here; it equals 1.0403

My second term is going to be 2; my third term is 5; and then, my fourth term is going to be 14.0410

And I could write this out as a sequence: 1, 2, 5, 14.0421

In the first example, I am asked to find the first 5 terms; and I am given that the first term is 3.0429

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.0435

So, if I am looking for a_{n + 1}, it is going to be equal to 2 times the previous term, minus 3.0448

And I need to find the first 5 terms.0456

Well, the first term is given (the first term is 3); and I need to find a₂.0458

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.0464

So, that is going to give me 2 times 3 minus 3, equals 6 - 3, which equals 3.0481

I found the second term; I need to find the third term.0489

So, I am going to take 2 times the previous term (the value of that is 3), minus 3.0493

You are starting to see a pattern here: again, we have 3.0499

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.0503

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.0508

So, this is actually a sequence where this formula generates the same value over and over and over.0521

So, I am just going to end up with a sequence that looks like this; and that is actually going to go on forever.0526

This is kind of an interesting formula where we ended up with the same value over and over and over in this sequence.0532

Example 2: this time we are going to work with iterates--we are asked to find the first three iterates of this function.0543

And the function is f(x) = 4x - 7, and x₀ = 3.0549

To find the first iterate, I am going to go ahead and find f(x₀, which equals 4.0555

And then, I am going to insert 3 here.0567

Actually, just to clarify: this is equal to f(3), because x₀ is 3.0569

So, we are going to write this as 4(3) - 7 = 12 - 7; that equals 5.0575

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).0582

That equals 4(5) - 7; that is going to give me 20 - 7, which is 13.0592

Next, f(f(f(x₀))): I know that this, in here, is 13, so I just take f(13) = 4(13) - 7.0600

4 times 13 is 52, minus 7 gives me 45; so I found the first three iterates, and those are 5, 13, and 45.0615

Example 3: Find the first five terms--they give me the first term; they give me the second term;0639

and they give me a formula that is a recursive formula, because it depends on the previous two terms.0645

So, a_n = 2(a_{n - 1}) + 3(a_{n - 2}).0653

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₅.0660

Let's start with a₃: a₃ is going to equal 2 times the term that came just before,0672

or a₂, plus 3 times the term before that, which is a₁.0682

This is going to be equal to 2 times 3, plus 3 times 2, equals 6 + 6; that is going to give me 12.0688

So, a₃ is 12; a₄ is going to be equal to 2 times a₃, plus 3 times a₂,0699

which equals 2 times...a₃ is 12, plus 3 times a₂, which is 3.0708

Of course, 2 times 12 is 24, plus 3 times 3 (is 9)...24 + 9 is 33: a₄ is 33.0717

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.0730

That is going to give me 66, plus 3 times 12 (is 36), and that adds up to 102.0742

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.0751

Find the first three iterates: f(x) = x² + 3x - 4; and then, x₀, or "x naught," is equal to 1.0763

The first iterate will be f(x₀), which equals f(1); that gives me 1² + 3(1) - 4, equals 1 - 3 - 4.0772

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.0790

The next iterate: f(f(x₀)): this is going to be equal to...since f(x₀) is 0, it is just f(0).0805

0² + 3(0) - 4 is 0 + 0 - 4; so that is going to give me -4.0817

Next, I want f(f(f(x₀))); this is going to be equal to f(-4) = (-4)² + 3(-4) - 4.0829

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.0847

That concludes this lesson of Educator.com; thanks for visiting, and see you soon!0869