Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.

Video: Recursive Sequences

Tim Burnham

We take a detailed look at the notation and method used to represent sequences of numbers using a recursive formula. This includes cases where one term is a function of its preceding term and others where it is a function of more than one previous term.

17:53

Video Transcript

In this video, we’re gonna look at how to specify a sequence of numbers using recursive notation, and then we’ll try some typical questions. A sequence is a list of numbers that’s generated using a consistent rule. For example, two, four, six, eight, ten, twelve and so on. This sequence starts with two, and then we add two to each term to get the next term. This way of describing a sequence by specifying the first term and setting out a term to term rule telling you what you need to do to one term to generate the next term in the sequence is called recursive. Now rather than writing out the description longhand like this, we can use some mathematical notation to specify the rule.

And in this case, we might put π‘Ž 𝑛 plus one is equal to an plus two, where π‘Ž one is equal to two and 𝑛 is greater than or equal to one and 𝑛 is an integer. Now this bit here tells you how the sequence begins. The first term π‘Ž one is equal to two. And this bit here sets up our numbering system for terms in the sequence, so we’re gonna have a first term, a second term, a third term, and so on. So 𝑛 is gonna be a series of integers starting at one. And this bit defines the term to term rule. It’s telling us that we need to take the value of a term at position 𝑛, add two to that, and that will then generate the next term in the sequence: the term at position 𝑛 plus one in the sequence.

So remember, π‘Ž 𝑛 means the term that’s at position 𝑛 in the sequence. So π‘Ž one means the first term in the sequence, π‘Ž two means the second term in the sequence, π‘Ž three means the third term in the sequence, and so on. So just before we move on, let’s make a point about this bit defining the values of 𝑛.

It’s important that we link the values of 𝑛 to the sequence formula. So we get π‘Ž one, π‘Ž two, π‘Ž three, π‘Ž four, et cetera and not π‘Ž zero or π‘Ž half or anything like that. So for example, if I’ve just said that 𝑛 is greater than or equal to zero, then putting that in here would have given us an π‘Ž zero term, and that’s not a proper term in our sequence. Likewise, if I’ve said 𝑛 is greater than or equal to two, then the smallest value that we could have got here is π‘Ž two. And we would have defined the first term in our sequence π‘Ž one, so that formula wouldn’t work properly.

Now another way of defining a recursive sequence for the sequence we were looking at is π‘Ž 𝑛 is equal to π‘Ž 𝑛 minus one plus two, and the first time is two. Now let’s think very careful about what values of 𝑛 we have to define if we put our sequence in this format. Well if 𝑛 took the values one, two, three, four, five, and so on, then we would have a case where we had π‘Ž one, 𝑛 is equal to one is equal to π‘Ž 𝑛 minus one is equal to π‘Ž zero plus two. And we can’t have a zeroth term because our terms need to be the first, second, third, fourth, and so on. So we need to start counting at two. So we’ve defined the first term as being two, and then we’ve got the second term is equal to the first term plus two.

Now with this sort of notation, if you know the value of any term in the sequence, you can easily work out the value of the next term. For example, if I had told you the hundred and second term was two hundred and four, then you could just add two to it to get the value of the hundred and third term. If the hundred and second term is two hundred and four, that means that π‘Ž one o two is two hundred and four. And following this pattern, π‘Ž 𝑛 plus one is equal to π‘Ž 𝑛 plus two, that means that π‘Ž one o three is equal to π‘Ž one o two plus two.

Well we’ve just said that the hundred and second term is two hundred and four, so we can replace that in our formula. So the hundred and third term is two hundred and four plus two, which is two hundred and six. But with a little bit of rearranging of the formula, you could also work out the value of the hundred and first term. Looking at the formula, if I subtract two from both sides of that equation, I get π‘Ž 𝑛 plus one minus two is equal to π‘Ž 𝑛. And now I’ve got a formula that tells me the current term if I know what the next term is. And next term take away two gives me the current term. Or the hundred and second term take away two gives me the hundred and first term, which means that two hundred and four take away two is the hundred and first term, which means the hundred and first term is two hundred and two.

This means that using our recursive formula, we can take any term in the sequence and work out what the next term was and what the previous term was. With a big downside to this way of doing things is if I want to know the millionth term, then you’ve got to do a lot of work to find out its value. You need to work out the value of the second term then apply the rule again to find the third term then the fourth and fifth and so on. The other way of specifying a sequence is using a position to term rule. So thinking back to our original sequence: two, four, five, eight, ten, twelve, and so on, if we write the position of each number in the sequence above the actual number, you might notice that the value of each term is equal to twice its position in the sequence. So two times one is two, two times two is four, two times three is six, two times four is eight, and so on.

This means that the value of a term in our sequence is equal to twice or two times the position in that sequence. Or π‘Ž 𝑛 is equal to two 𝑛 in this case. Now it’s worth just taking a moment to remind you that this 𝑛 here is a suffix or a subscript, a little 𝑛 just below π‘Ž, whereas this 𝑛 here is a proper full-size 𝑛 right up against the two, which means two times 𝑛. So just watch out for that. When I say π‘Ž 𝑛, I don’t mean π‘Ž times 𝑛 in this case. I mean π‘Ž suffix 𝑛.

Now the great thing about this formula is it takes you straight to the value of the term if you know it’s position. So the millionth term π‘Ž a million is just equal to two times a million, which is two million. Now just compare how long that would have taken to work out the seventh term, the eighth, and the ninth term, and so on all the way up to the millionth term using the recursive formula.

Anyway back to the point of this video, recursive sequences. Let’s try some questions. Find the first three terms of the sequence π‘Ž 𝑛 plus one is equal to two times π‘Ž 𝑛 plus five, where the first term π‘Ž one is eleven and 𝑛 is greater than or equal one and 𝑛 is an integer. Now this formula tells that if we take a term and we double it, and then we add five to that, we get the value of the next term in the sequence. To calculate the second term, we double the first term and add five. And the first term is eleven. That’s what we were told in the question. And that means the second time is two times eleven plus five, which is twenty-two plus five which is twenty-seven.

And now we can use that information to work out the third term. The third term is equal to two times the second term plus five. So that’s two times twenty-seven plus five, which is fifty-four plus five which is fifty-nine. So now we’ve got the first three terms: eleven, twenty-seven, and fifty-nine.

Next question then. Find the first four terms in the sequence π‘Ž 𝑛 plus one is equal to a half of π‘Ž 𝑛 minus four, where π‘Ž two is thirty-six and 𝑛 is greater than or equal to one, 𝑛 is an integer. Well this is a bit tricky because we’ve been told what the second term is, but we don’t know what the first time is. So we’ve got to work that out. And the formula was telling us if we take a term and halve it and then subtract four, it gives us our next term.

So for an example, π‘Ž two, the second term, is equal to a half times π‘Ž one, so a half of the first term take away four. We were told that the value of the second term was thirty-six, so we know that thirty-six is equal to a half times π‘Ž one minus four. Now I wanna work out what π‘Ž one is. So if I add four to both sides of that equation, I get forty is equal to a half of π‘Ž one, the first term. And if I double both sides of the equation, I find that the first term must have been eighty.

And we can apply our recursive formula to work out what the third term is. Remember, to find the next term we have to halve this term and then subtract four. So the third term is a half of the second term take away four. And we know what the second term is. It’s thirty-six. So the third time is a half of thirty-six take away four. Well half of thirty-six is eighteen. And eighteen take away four is fourteen. And lastly, the fourth term is a half of third term take away four. And we’ve just worked out the third term was fourteen, which means that the fourth term turns out to be three. So to answer our question, the first term is eighty, the second is thirty-six, the third term is fourteen, and the fourth term is three.

Let’s have a look at a slightly more complicated recursive sequence then. Find the first five terms in the sequence π‘Ž 𝑛 is equal to two times π‘Ž 𝑛 minus one plus π‘Ž 𝑛 minus two, where π‘Ž one is three and π‘Ž two is five, and 𝑛 is greater than or equal to three. And 𝑛 is an integer. Now this formula is telling us that a term is some combination of the previous two terms. It’s twice the immediately preceding term, and then we have to add on the term before that. And to get this sort of formula going, we need to provide two initial terms, the first and the second term, to enable you to work out the third term. And now 𝑛 is greater than or equal to three, If 𝑛 was less than three, if 𝑛 started at two, then we’d have the second term is equal to the first term, two times the first times plus the zeroth term. So that wouldn’t work. So this recursive sequences is only set up for 𝑛 is greater than or equal to three.

Well the question asked us to work out the first five terms. We’ve already been given the first two, so let’s have a go at working out the third one. And as we’ve said in the formula, to work out a particular term, we double the previous term: 𝑛 minus one, and then we add on the term before that: 𝑛 minus two. Let’s just plug in those values for π‘Ž one and π‘Ž two then. So π‘Ž two is five and π‘Ž one is three, so π‘Ž three is two times five plus three, which is ten plus three and that’s thirteen.

Now the fourth term is twice the third term plus the second term. And that’s two times thirteen plus five. We’ve just worked out the third term. Well two times thirteen is twenty-six and twenty-six plus five is thirty-one. And finally, the fifth term is two times the fourth term plus the third term. And plugging in the values of the fourth and third terms that we’ve just worked out, we can see that the fifth term is seventy-five. And we just need to write all those out in full for our answer. And that’s a basic run through how to use recursive formulae.

Now some sequences are arithmetic sequences and that means that each consecutive term has got a common difference. For example, three, seven, eleven, fifteen, nineteen, and so on, I have to add four to each term to get the next term. That makes it an arithmetic sequence. And twenty-three, twenty-one, nineteen, seventeen, fifteen, and so on, I’m having to subtract two from each term to get the next term. And that’s also an arithmetic sequence. And we can represent each of these using recursive formula. In the first case, one term is equal to the previous term plus four. But don’t forget we have to tell it where to start, and the 𝑛 is greater than or equal to one in this case. And for the second sequence, one term is equal to the previous term take away two. And again, we have to tell it where to start and the relevant values of 𝑛.

Now let’s just rearrange this formulae. For the first one, π‘Ž 𝑛 plus one equals π‘Ž 𝑛 plus four. I’m gonna subtract π‘Ž 𝑛 from both sides, which gives me π‘Ž 𝑛 plus one minus π‘Ž 𝑛 is equal to four. Well π‘Ž 𝑛 plus one minus π‘Ž 𝑛, that’s the difference between two consecutive terms. And this formula is telling me that that’s always constant. It’s always four in this case. And if I do the same with the other formula, I find that in this case the difference between two consecutive terms is also a constant negative two in this case. So if you’ve got a recursive formula which you can rearrange to get the difference between two consecutive terms, and that answer just comes out to be a constant, then you know that you’re looking at an arithmetic sequence. And that’s just an algebraic way of saying that you know every time I go from one term to the other, I’m always adding the same amount.

Lastly then, let’s take a look at a couple of sequences and see if we can write down a recursive formula for each one. Write down a recursive formula for the sequence five, seven, nine, eleven, thirteen, and so on. Well a good place to start is to work out what’s the difference between each term. To get from five to seven, I need to add two. From seven to nine, add two. And to get between the next two terms, I add two and the next two terms again, I add two again. And it’s a good idea to try to describe what’s going on before you try to put it into a formula. So to get from one term to the next, I’m adding two every time. And in our formula then, if I take a term β€” let’s call it π‘Ž 𝑛 β€” and I add two to that term is going to give me the next term π‘Ž 𝑛 plus one.

Well actually, its sort of as easy as that. That’s the basic formula, but we do need to tell it where to start and we need to define the values of 𝑛 that are going to work in this formula. Well our first term was five, so π‘Ž one is five And we want to use values of 𝑛 that generate terms π‘Ž one, π‘Ž two, π‘Ž three, π‘Ž four, π‘Ž five, and so on. Now in our formula, we’ve got π‘Ž 𝑛 and then we’ve got π‘Ž 𝑛 plus one. So we can have 𝑛 has all the values from one upwards. So that’s our formula: π‘Ž 𝑛 plus one equals π‘Ž 𝑛 plus two where π‘Ž one is five and 𝑛 is greater than or equal to one and 𝑛 is an integer.

Now I could have formulated that slightly differently, so I could have said the 𝑛th term, π‘Ž 𝑛, is simply equal to the previous term π‘Ž 𝑛 minus one plus two. And again, the first term π‘Ž one is equal to five. But lets think about the values of 𝑛. If I put 𝑛 equal to one, I’d be saying π‘Ž one, the first term, is equal to π‘Ž one minus one, π‘Ž zero. I’d be talking about the zeroth term plus two. And I don’t have a zeroth term, so I’m gonna define 𝑛 from two onwards. That gives me an alternative recursive formula.

Right then, one last tricky question. Write down a recursive formula for the sequence three, nine, twenty-one, forty-five, ninety-three, and so on. Now again, good starting point is to actually say well what’s the difference between each term and the next term. So to get from three to nine, I need to add six. But to get from nine to twenty-one, I need to add twelve. To get from twenty-one to forty-five, I need to add twenty-four. And to get from forty-five to ninety-three, I need to add forty-eight. So this isn’t an arithmetic sequence. This is a bit of a trickier prospect.

Now if you look at each term and then you look at the differences, we can see that in the first case we start off with three, but we’re adding six. Then we s- then we start off with nine, and we’re adding twelve. We start off with twenty-one and we’re adding twenty-four. We start off with forty-five, we’re adding forty-eight. These differences are always three more than the previous term. Now if we label our terms π‘Ž one, π‘Ž two, π‘Ž three, π‘Ž four, π‘Ž five, and so on, the second term is equal to the first term plus six. And the third term is equal to the second term plus twelve. But we said that the difference is three bigger than the term, the previous term itself, so this difference is three bigger than this. So six is π‘Ž one plus three. And for working out a third term, that twelve, that difference there, is the second term plus three again. So the third term is equal to the second term plus the second term plus three, and that’s gonna be the case generally.

The 𝑛 plus oneth term is equal to the 𝑛th term plus the 𝑛th term plus three. And given that this is just three values added together β€” I don’t need those parentheses β€” that gives me π‘Ž 𝑛 plus π‘Ž 𝑛 plus three. That’s two lots of π‘Ž 𝑛 plus three. So π‘Ž 𝑛 plus one is equal to two π‘Ž 𝑛 plus three. And now we need to think about the starting conditions. Well the first term π‘Ž one is equal to three. And to generate terms π‘Ž one, π‘Ž two, π‘Ž three, π‘Ž four, and so on, I need to put 𝑛 equal to one, two, three, and so on. So that’s it. There’s my formula. Now I could adjust this slightly as well like I did the last time. And that will give me the 𝑛th term is equal to two times the 𝑛 minus oneth term plus three. And again I’d have to adjust the starting point of 𝑛; 𝑛 is greater than or equal two, so that I don’t end up with the term π‘Ž zero.