Sign In | Subscribe
INSTRUCTORSCarleen EatonGrant Fraser
Start learning today, and be successful in your academic & professional career. Start Today!
Loading video...
This is a quick preview of the lesson. For full access, please Log In or Sign up.
For more information, please see full course syllabus of Algebra 2
  • Discussion

  • Study Guides

  • Practice Questions

  • Download Lecture Slides

  • Table of Contents

  • Transcription

  • Related Books

Bookmark and Share

Start Learning Now

Our free lessons will get you started (Adobe Flash® required).
Get immediate access to our entire library.

Sign up for Educator.com

Membership Overview

  • Unlimited access to our entire library of courses.
  • Search and jump to exactly what you want to learn.
  • *Ask questions and get answers from the community and our teachers!
  • Practice questions with step-by-step solutions.
  • Download lesson files for programming and software training practice.
  • Track your course viewing progress.
  • Download lecture slides for taking notes.
  • Learn at your own pace... anytime, anywhere!

Recursion and Special Sequences

  • If a sequence is defined so that it depends on the value of the previous term, then to find the kth term, you must first compute terms 2, 3, 4, …, and k – 1. You will be given the first term.
  • This same comment applies to finding the kth iterate of a function. You must first compute the 1st, 2nd, …, and (k – 1)st iterates.
  • In calculating iterates, always evaluate each iterate for the numerical value x0 you are given.

Recursion and Special Sequences

Find the first 3 iterates
f(x) = x2 − 9,x0 = 0
  • Plug in the vale of x0 = 0 into the function to find the first iterate
  • f(x0) = f(0) =
  • f(x0) = f(0) = (0)2 − 9 = − 9
  • To find the second iterate, plug into the function f(f(x0))
  • f(f(x0)) = f( − 9) =
  • f(f(x0)) = f( − 9) = ( − 9)2 − 9 = 81 − 9 = 72
  • To find the third iterate, plug into the function f(f(f(x0))) =
  • f(f(f(x0))) = f(72) =
  • f(f(f(x0))) = f(72) = (72)2 − 9 = 5184 − 9 = 5175
First 3 iterates are − 9;72;5175
Find the first 3 iterates
f(x) = x3 − 10x2,x0 = 3
  • Plug in the vale of x0 = 3 into the function to find the first iterate
  • f(x0) = f(3) =
  • f(x0) = f(3) = (3)3 − 10(3)2 = 27 − 90 = − 63
  • To find the second iterate, plug into the function f(f(x0))
  • f(f(x0)) = f( − 63) =
  • f(f(x0)) = f( − 63) = ( − 63)3 − 10( − 63)2 = − 250047 − 39690 = − 289737
  • To find the third iterate, plug into the function f(f(f(x0))) =
  • f(f(f(x0))) = f( − 289737) =
  • f(f(f(x0))) = f( − 289737) = ( − 289737)3 − 10( − 289737 )2 = − 24,322,705,258,838,553 − 839,475,291,690 = − 24,323,544,734,130,243
First 3 iterates are − 63; − 289737; − 24,323,544,734,130,243
Find the first 3 iterates
f(x) = x2 − 100x,x0 = 2
  • Plug in the vale of x0 = 2 into the function to find the first iterate
  • f(x0) = f(2) =
  • f(x0) = f(2) = (2)2 − 100(2) = 4 − 200 = − 196
  • To find the second iterate, plug into the function f(f(x0))
  • f(f(x0)) = f( − 196) =
  • f(f(x0)) = f( − 196) = ( − 196)2 − 100( − 196) = 38416 + 19600 = 58,016
  • To find the third iterate, plug into the function f(f(f(x0))) =
  • f(f(f(x0))) = f(58016) =
  • f(f(f(x0))) = f(58016) = (58016)2 − 100( 58016 ) = 3365856256 − 5801600 = 3360054656
First 3 iterates are − 196; 58016; 3360054656
Find the first 3 iterates
f(x) = 5x + 10,x0 = 5
  • Plug in the vale of x0 = 2 into the function to find the first iterate
  • f(x0) = f(5) =
  • f(x0) = f(5) = 5(5) + 10 = 25 + 10 = 35
  • To find the second iterate, plug into the function f(f(x0))
  • f(f(x0)) = f(35) =
  • f(f(x0)) = f(35) = 5(35) + 10 = 175 + 10 = 185
  • To find the third iterate, plug into the function f(f(f(x0))) =
  • f(f(f(x0))) = f(185) =
  • f(f(f(x0))) = f(185) = 5(185) + 10 = 925 + 10 = 935
First 3 iterates are 35; 185; 935
Find the first 3 iterates
f(x) = 10x − 6,x0 = 10
  • Plug in the vale of x0 = 2 into the function to find the first iterate
  • f(x0) = f(10) =
  • f(x0) = f(10) = 10(10) − 6 = 100 − 6 = 94
  • To find the second iterate, plug into the function f(f(x0))
  • f(f(x0)) = f(94) =
  • f(f(x0)) = f(94) = 10(94) − 6 = 940 − 6 = 934
  • To find the third iterate, plug into the function f(f(f(x0))) =
  • f(f(f(x0))) = f(934) =
  • f(f(f(x0))) = f(934) = 10(934) − 6 = 9340 − 6 = 9334
First 3 iterates are 94; 934; 9334
Write the first five terms of the sequence
a1 = − 4
an = an − 1 + 5
  • When working with recursive formulas, each term is used to produce the next term.
  • a1 = − 4
  • a2 = a2 − 1 + 5 = a1 + 5 = − 4 + 5 = 1
  • a3 = a3 − 1 + 5 = a2 + 5 = 1 + 5 = 6
  • a4 = a4 − 1 + 5 = a3 + 5 = 6 + 5 = 11
  • a5 = a5 − 1 + 5 = a4 + 5 = 11 + 5 = 16
a2 = 1; a3 = 6; a4 = 11; a5 = 16
Write the first five terms of the sequence
a1 = 3 an = ( − 1)n*5an − 1
  • When working with recursive formulas, each term is used to produce the next term.
  • a1 = 3
  • a2 = ( − 1)2*5a2 − 1 = ( − 1)2*5a1 = ( − 1)2*5(3) = 15
  • a3 = ( − 1)3*5a3 − 1 = ( − 1)3*5a2 = ( − 1)3*5(15) = − 75
  • a4 = ( − 1)4*5a4 − 1 = ( − 1)4*5a3 = ( − 1)4*5( − 75) = − 375
  • a5 = ( − 1)5*5a5 − 1 = ( − 1)5*5a4 = ( − 1)5*5( − 375) = 1875
a1 = 3; a2 = 15; a3 = 75; a4 = 375; a5 = 18755
Write the first five terms of the sequence
a1 = 6
an = [1/2]*an − 1 + 4
  • When working with recursive formulas, each term is used to produce the next term.
  • a1 = 6
  • a2 = [1/2]*an − 1 + 4 = [1/2]*a2 − 1 + 4 = [1/2]*a1 + 4 = [1/2]*6 + 4 = 3 + 4 = 7
  • a3 = [1/2]*a3 − 1 + 4 = [1/2]*a3 − 1 + 4 = [1/2]*a2 + 4 = [1/2]*7 + 4 = 3.5 + 4 = 7.5
  • a4 = [1/2]*a4 − 1 + 4 = [1/2]*a4 − 1 + 4 = [1/2]*a3 + 4 = [1/2]*7.5 + 4 = 3.75 + 4 = 7.75
  • a5 = [1/2]*a5 − 1 + 4 = [1/2]*a5 − 1 + 4 = [1/2]*a4 + 4 = [1/2]*7.75 + 4 = 3.875 + 4 = 7.875
a1 = 6; a2 = 7; a3 = 7.5; a4 = 7.75; a5 = 7.875
Write the first five terms of the sequence
a1 = 1 an = [(an − 1 + 3)/2]
  • When working with recursive formulas, each term is used to produce the next term.
  • a1 = 1
  • a2 = [(an − 1 + 3)/2] = [(a2 − 1 + 3)/2] = [(a1 + 3)/2] = [(1 + 3)/2] = 2
  • a3 = [(a3 − 1 + 3)/2] = [(a3 − 1 + 3)/2] = [(a2 + 3)/2] = [(2 + 3)/2] = 2.5
  • a4 = [(a4 − 1 + 3)/2] = [(a4 − 1 + 3)/2] = [(a3 + 3)/2] = [(2.5 + 3)/2] = 2.75
  • a5 = [(a5 − 1 + 3)/2] = [(a5 − 1 + 3)/2] = [(a4 + 3)/2] = [(2.75 + 3)/2] = 2.875
a1 = 1; a2 = 2; a3 = 2.5; a4 = 2.75; a5 = 2.875

*These practice questions are only helpful when you work on them offline on a piece of paper and then use the solution steps function to check your answer.

Answer

Recursion and Special Sequences

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

  • Intro 0:00
  • Fibonacci Sequence 0:05
    • Background of Fibonacci
    • Recursive Formula
    • Fibonacci Sequence
    • Example: Recursive Formula
  • Iteration 3:49
    • Example: Iteration
  • Example 1: Five Terms 7:08
  • Example 2: Three Terms 9:00
  • Example 3: Five Terms 10:38
  • Example 4: Three Iterates 12:41

Transcription: 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, an, is equal to the previous two terms,0006

an - 1 + an - 2--the term that came just before it and the one before that.0016

Fibonacci is an Italian mathematician who lived in the 13th 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, a3 is going to be equal to the term that came just before it, an - 1 (and 3 - 10070

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

a3 = 1 + 1, or 2; a4...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, an = 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 a3?"--well, a3 = 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, a3 = 8 + 2, which is actually going to be 10.0188

So, in this case, I was given a formula, an 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 x0, or "x naught."0264

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

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

So, I could be asked to find the first iterate; I am going to find f(x0), 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(x0)), 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(x0))).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(x0)))).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, a1, 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 an + 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 a2.0458

a2 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 x0 = 3.0549

To find the first iterate, I am going to go ahead and find f(x0, 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 x0 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(x0)), 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(x0))): 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, an = 2(an - 1) + 3(an - 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 a3, a4, and a5.0660

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

or a2, plus 3 times the term before that, which is a1.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, a3 is 12; a4 is going to be equal to 2 times a3, plus 3 times a2,0699

which equals 2 times...a3 is 12, plus 3 times a2, which is 3.0708

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

a5 is equal to 2 times a4, plus 3 times a3; 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) = x2 + 3x - 4; and then, x0, or "x naught," is equal to 1.0763

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

So, I have, let me see...actually, that is plus right here...so that is 12 + 3 - 4, so 1 + 3 - 4; that is 4 - 4; the first iterate is 0.0790

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

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

Next, I want f(f(f(x0))); this is going to be equal to f(-4) = (-4)2 + 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