## Discussion

## Study Guides

## Practice Questions

## Download Lecture Slides

## Table of Contents

## Transcription

## Related Books

### 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 1
^{st}, 2^{nd}, …, and (k – 1)st iterates. - In calculating iterates, always evaluate each iterate for the numerical value x
_{0}you are given.

### Recursion and Special Sequences

f(x) = x

^{2}− 9,x

_{0}= 0

- Plug in the vale of x
_{0}= 0 into the function to find the first iterate - f(x
_{0}) = f(0) = - f(x
_{0}) = f(0) = (0)^{2}− 9 = − 9 - To find the second iterate, plug into the function f(f(x
_{0})) - f(f(x
_{0})) = f( − 9) = - f(f(x
_{0})) = f( − 9) = ( − 9)^{2}− 9 = 81 − 9 = 72 - To find the third iterate, plug into the function f(f(f(x
_{0}))) = - f(f(f(x
_{0}))) = f(72) = - f(f(f(x
_{0}))) = f(72) = (72)^{2}− 9 = 5184 − 9 = 5175

f(x) = x

^{3}− 10x

^{2},x

_{0}= 3

- Plug in the vale of x
_{0}= 3 into the function to find the first iterate - f(x
_{0}) = f(3) = - f(x
_{0}) = f(3) = (3)^{3}− 10(3)^{2}= 27 − 90 = − 63 - To find the second iterate, plug into the function f(f(x
_{0})) - f(f(x
_{0})) = f( − 63) = - f(f(x
_{0})) = f( − 63) = ( − 63)^{3}− 10( − 63)^{2}= − 250047 − 39690 = − 289737 - To find the third iterate, plug into the function f(f(f(x
_{0}))) = - f(f(f(x
_{0}))) = f( − 289737) = - f(f(f(x
_{0}))) = f( − 289737) = ( − 289737)^{3}− 10( − 289737 )^{2}= − 24,322,705,258,838,553 − 839,475,291,690 = − 24,323,544,734,130,243

f(x) = x

^{2}− 100x,x

_{0}= 2

- Plug in the vale of x
_{0}= 2 into the function to find the first iterate - f(x
_{0}) = f(2) = - f(x
_{0}) = f(2) = (2)^{2}− 100(2) = 4 − 200 = − 196 - To find the second iterate, plug into the function f(f(x
_{0})) - f(f(x
_{0})) = f( − 196) = - f(f(x
_{0})) = f( − 196) = ( − 196)^{2}− 100( − 196) = 38416 + 19600 = 58,016 - To find the third iterate, plug into the function f(f(f(x
_{0}))) = - f(f(f(x
_{0}))) = f(58016) = - f(f(f(x
_{0}))) = f(58016) = (58016)^{2}− 100( 58016 ) = 3365856256 − 5801600 = 3360054656

f(x) = 5x + 10,x

_{0}= 5

- Plug in the vale of x
_{0}= 2 into the function to find the first iterate - f(x
_{0}) = f(5) = - f(x
_{0}) = f(5) = 5(5) + 10 = 25 + 10 = 35 - To find the second iterate, plug into the function f(f(x
_{0})) - f(f(x
_{0})) = f(35) = - f(f(x
_{0})) = f(35) = 5(35) + 10 = 175 + 10 = 185 - To find the third iterate, plug into the function f(f(f(x
_{0}))) = - f(f(f(x
_{0}))) = f(185) = - f(f(f(x
_{0}))) = f(185) = 5(185) + 10 = 925 + 10 = 935

f(x) = 10x − 6,x

_{0}= 10

- Plug in the vale of x
_{0}= 2 into the function to find the first iterate - f(x
_{0}) = f(10) = - f(x
_{0}) = f(10) = 10(10) − 6 = 100 − 6 = 94 - To find the second iterate, plug into the function f(f(x
_{0})) - f(f(x
_{0})) = f(94) = - f(f(x
_{0})) = f(94) = 10(94) − 6 = 940 − 6 = 934 - To find the third iterate, plug into the function f(f(f(x
_{0}))) = - f(f(f(x
_{0}))) = f(934) = - f(f(f(x
_{0}))) = f(934) = 10(934) − 6 = 9340 − 6 = 9334

a

_{1}= − 4

a

_{n}= a

_{n − 1}+ 5

- When working with recursive formulas, each term is used to produce the next term.
- a
_{1}= − 4 - a
_{2}= a_{2 − 1}+ 5 = a_{1}+ 5 = − 4 + 5 = 1 - a
_{3}= a_{3 − 1}+ 5 = a_{2}+ 5 = 1 + 5 = 6 - a
_{4}= a_{4 − 1}+ 5 = a_{3}+ 5 = 6 + 5 = 11 - a
_{5}= a_{5 − 1}+ 5 = a_{4}+ 5 = 11 + 5 = 16

_{2}= 1; a

_{3}= 6; a

_{4}= 11; a

_{5}= 16

a

_{1}= 3 a

_{n}= ( − 1)

^{n}*5a

_{n − 1}

- When working with recursive formulas, each term is used to produce the next term.
- a
_{1}= 3 - a
_{2}= ( − 1)^{2}*5a_{2 − 1}= ( − 1)^{2}*5a_{1}= ( − 1)^{2}*5(3) = 15 - a
_{3}= ( − 1)^{3}*5a_{3 − 1}= ( − 1)^{3}*5a_{2}= ( − 1)^{3}*5(15) = − 75 - a
_{4}= ( − 1)^{4}*5a_{4 − 1}= ( − 1)^{4}*5a_{3}= ( − 1)^{4}*5( − 75) = − 375 - a
_{5}= ( − 1)^{5}*5a_{5 − 1}= ( − 1)^{5}*5a_{4}= ( − 1)^{5}*5( − 375) = 1875

_{1}= 3; a

_{2}= 15; a

_{3}= 75; a

_{4}= 375; a

_{5}= 18755

a

_{1}= 6

a

_{n}= [1/2]*a

_{n − 1}+ 4

- When working with recursive formulas, each term is used to produce the next term.
- a
_{1}= 6 - a
_{2}= [1/2]*a_{n − 1}+ 4 = [1/2]*a_{2 − 1}+ 4 = [1/2]*a_{1}+ 4 = [1/2]*6 + 4 = 3 + 4 = 7 - a
_{3}= [1/2]*a_{3 − 1}+ 4 = [1/2]*a_{3 − 1}+ 4 = [1/2]*a_{2}+ 4 = [1/2]*7 + 4 = 3.5 + 4 = 7.5 - a
_{4}= [1/2]*a_{4 − 1}+ 4 = [1/2]*a_{4 − 1}+ 4 = [1/2]*a_{3}+ 4 = [1/2]*7.5 + 4 = 3.75 + 4 = 7.75 - a
_{5}= [1/2]*a_{5 − 1}+ 4 = [1/2]*a_{5 − 1}+ 4 = [1/2]*a_{4}+ 4 = [1/2]*7.75 + 4 = 3.875 + 4 = 7.875

_{1}= 6; a

_{2}= 7; a

_{3}= 7.5; a

_{4}= 7.75; a

_{5}= 7.875

a

_{1}= 1 a

_{n}= [(a

_{n − 1}+ 3)/2]

- When working with recursive formulas, each term is used to produce the next term.
- a
_{1}= 1 - a
_{2}= [(a_{n − 1}+ 3)/2] = [(a_{2 − 1}+ 3)/2] = [(a_{1}+ 3)/2] = [(1 + 3)/2] = 2 - a
_{3}= [(a_{3 − 1}+ 3)/2] = [(a_{3 − 1}+ 3)/2] = [(a_{2}+ 3)/2] = [(2 + 3)/2] = 2.5 - a
_{4}= [(a_{4 − 1}+ 3)/2] = [(a_{4 − 1}+ 3)/2] = [(a_{3}+ 3)/2] = [(2.5 + 3)/2] = 2.75 - a
_{5}= [(a_{5 − 1}+ 3)/2] = [(a_{5 − 1}+ 3)/2] = [(a_{4}+ 3)/2] = [(2.75 + 3)/2] = 2.875

_{1}= 1; a

_{2}= 2; a

_{3}= 2.5; a

_{4}= 2.75; a

_{5}= 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

### Algebra 2

### 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, 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 _{3} is going to be equal to the term that came just before it, a_{n - 1} (and 3 - 1*0070

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

*a _{3} = 1 + 1, or 2; a_{4}...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 formula*0135

*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 _{3}?"--well, a_{3} = 4 times the term*0169

*that came just before, which is 2, plus 2 times the term before that, which is equal to 1.*0178

*So here, a _{3} = 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 _{0}, or "x naught."*0264

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

*f(x) = 3x - 1; x _{0} = 1; so I have been given my function, and I am given this x_{0}.*0272

*So, I could be asked to find the first iterate; I am going to find f(x _{0}), 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 _{0})), 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 _{0}))).*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 _{0})))).*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 _{1}, 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 _{2}.*0458

*a _{2} 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 _{0} = 3.*0549

*To find the first iterate, I am going to go ahead and find f(x _{0}, 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 _{0} 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 _{0})), 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 _{0}))): 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 _{3}, a_{4}, and a_{5}.*0660

*Let's start with a _{3}: a_{3} is going to equal 2 times the term that came just before,*0672

*or a _{2}, plus 3 times the term before that, which is a_{1}.*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 _{3} is 12; a_{4} is going to be equal to 2 times a_{3}, plus 3 times a_{2},*0699

*which equals 2 times...a _{3} is 12, plus 3 times a_{2}, which is 3.*0708

*Of course, 2 times 12 is 24, plus 3 times 3 (is 9)...24 + 9 is 33: a _{4} is 33.*0717

*a _{5} is equal to 2 times a_{4}, plus 3 times a_{3}; 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 ^{2} + 3x - 4; and then, x_{0}, or "x naught," is equal to 1.*0763

*The first iterate will be f(x _{0}), which equals f(1); that gives me 1^{2} + 3(1) - 4, equals 1 - 3 - 4.*0772

*So, I have, let me see...actually, that is plus right here...so that is 1 ^{2} + 3 - 4, so 1 + 3 - 4; that is 4 - 4; the first iterate is 0.*0790

*The next iterate: f(f(x _{0})): this is going to be equal to...since f(x_{0}) is 0, it is just f(0).*0805

*0 ^{2} + 3(0) - 4 is 0 + 0 - 4; so that is going to give me -4.*0817

*Next, I want f(f(f(x _{0}))); 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

## Start Learning Now

Our free lessons will get you started (Adobe Flash

Sign up for Educator.com^{®}required).Get immediate access to our entire library.

## Membership Overview

Unlimited access to our entire library of courses.Learn at your own pace... anytime, anywhere!