دنباله های بازگشتی

Recursive Sequences

In the previous two videos, we talked about sequences that have an algebraic definition for each term, a sub n. If we have a clear formula for a sub n in terms of the index variable n, then we can calculate the value of any term we want. That is one way to define a sequence. And so that includes both the algebraic sequences, as well as arithmetic sequences for which we can construct a formula.

This video is about a whole other category of sequences to find in a very different way. To discuss this category, I will begin with a famous sequence from the history of mathematics: the Fibonacci sequence. This is the Fibonacci sequence. What is the pattern here?

It’s not clear at all just glancing at this, that there’s a discernible pattern. The first two numbers which I’m going to call the seed numbers, are both equal to one. And incidentally, this term seed numbers, this is not a widely used term. Some books use this term, but you will not see this everywhere. But this is the term I’ll be using in this video, the starting numbers, the seed numbers.

So we have two ones. Then we get the 2 just from adding those two ones. We get the 3 by adding the 1 and the 2 before it. Then we get the 5 by adding the 2 and the 3 before it. Then we get the 8 by adding the 3 and the 5 before it. After the first two seed numbers, we get each term by adding the two terms before it.

That’s the pattern here. First of all, I want to be clear. The test will not expect you to look at a sequence of numbers and recognize a pattern such as this for yourself. That is well beyond anything the test would expect.

But, the test will expect you to understand the algebraic representations of such sequences. And so we need to talk about that. Let’s think about this. A sub n is the nth term on the sequence. It’s the nth number on the list.

Now in a recursive sequence, this is going to be defined in terms say, of the number directly before it on the list. The term directly before it would have an index number that is one less, n minus 1. So a sub n minus 1 is the term immediately before the nth term. If a sub n is defined in terms of a sub n minus 1. This is called a recursive definition, and the sequence is a recursive sequence.

That is to say a sequence in which each term is defined in terms of the previous term or in terms of previous terms. In a recursive sequence, the nth term is defined in terms of either the single previous term, or as we’ll see in a moment, several, multiple previous terms. The test would have to give us a formula for a sub n in terms of a sub, a sub n minus 1.

And it would have have to give us a typical seed value, typically the value of the first term. So, the, the test would give us that and we need to recognize that it is a recursive sequence and we need to recognize what to do. So for example, here’s a very simple recursive sequence. We have a seed term.

Let’s just play around with this. We know that the first term is 1. Well what’s the second term? Well, the second term would be 2 times the first term plus 1. That’s 2 times 1, plus 1, which is 3. The third term would be 2 times the second term plus 1.

Well, that’s 2 times 3 plus 1, which is 7. The fourth term is 2 times the third term, plus 1. So this would be 2 times 7 plus 1, that’s 15. . The 15th term would be 2 times the fourth term plus 1. So this would be 2 times 15 plus 1.

This is 31. Notice that for a recursive sequence, there’s no way to jump right away to the value say, of a sub 5. The fifth number on the list. We have to work our way term by term from the starting seed up to the value we want. So this is very different from the algebraically defined sequences.

Where arithmetic sequences, we can’t just jump to a later term. We have to ratchet our way up term by term, finding every term along the way up to the term that’s desired. So obviously, the test is never gonna ask you to find say, the fortieth term. It’s gonna ask something more like just find the fifth or sixth term. Something where you’d only have to do a few steps of the calculation.

Here’s a practice question. Pause the video and then we’ll talk about this. Okay. We have a recursively fined, defined sequence. We have a seed value.

So the first term is clearly 1. The second term is the first term minus 1 squared plus 3. So 1 minus 1 is 0 plus 3, that just gives us 3. So the second term is 3. Now the third term is gonna be that second term minus 1. We’re gonna square that plus 3.

So that’s gonna be 2 squared, which is 4, plus 3, which is 7. The fourth term now. We’re gonna take 7. We’re gonna subtract 1. We’re gonna square it and add 3. And this gives us 39.

And that is the fourth term of this sequence. Those were examples in which each term depends on the term immediately before it. In some sequences, such as the Fibonacci sequence mentioned earlier, these depend on the previous two terms. For the hardest recursive sequences on the test, a sub n will be defined in terms of both a sub n minus 1, which is the immediately previous term.

And a sub n minus 2, which is the term before the previous term. So these are the two preceding terms. Think about the Fibonacci sequence again. This sequence has the two “seed” values. The first value is 1. The second value is 1.

And each term is the sum of the two previous terms. So algebraically, we would say a sub n equals a sub n minus 1 plus a sub n minus 2. That’s a symbolic representation of the rule that creates the Fibonacci sequence. For a sequence that has the same rules of the Fibonacci sequence but different seed values, different starting values, find the value of a sub 6.

So pause the video here and then we’ll talk about this. Okay. So, we have our seed values, 1 and 3. The fourth term, we’re going to add those two. So it’s going to be 4.

The fourth term, we’re gonna add the second and third term. 3 plus 4, which is 7. For the fifth term, we’re gonna add the fourth term and the third term. So that will be 7 plus 4, which is 11. And then to find the sixth term, we’d have to add the fifth term plus the fourth term.

So this would be 11 plus 7, which is 18. And that’s the sixth term on the list. Here’s a practice problem. Pause the video, and then we’ll talk about this. A sequence is defined by s sub n equals s sub n minus 1, quantity minus 1, times s sub n minus 2, for all n greater than 2.

And it has the starting values of s sub one equals 2 and s sub 2 equals 3. Find the value of s sub six. So once again, there’s no way to jump right away to, to the sixth term on the list. We have to find them in order. The third term, the fourth term, the fifth term, up to the sixth term.

So these are our starting terms. The third term is going to be the second term minus one. So 3 minus 1 is 2 times the first term 2. That’s 2 times 2, which is four. The fourth term is going to be the s sub 3, which is four. So 4 minus 1 is 3, times the second term which is 3.

We get 3 times 3, which is 9. That’s interesting. It looks like we’re getting squares. We wonder will that pattern continue? The fifth term is going to be the fourth term minus 1. So 9 minus 1 is 8, times the third term, which is 4.

8 times 4, that’s 32. So we don’t continue with squares. It looks like they get bigger. Now the 6th term. We’re ready for the 6th term. This is going to be the 5th term minus 1.

32 minus 1, which is 31 times 9. And 31 times 9, we can do that without a calculator. 30 times 9 is 270. So 31 times 9 is 279. And that is the sixth term on the list. In recursive sequences, each term a sub n is defined in terms of one or two previous terms.

It’s defined in terms of a sub n minus 1 and maybe in terms of a sub n minus 2. Numeric, numerical values for one or two terms will always be specified. With a recursive sequence, there is no way to jump immediately to the value of a term such as the sixth term. Instead, we have to find each and every term from the start up to the desired term.