A recursive rule builds each term from the ones before it

0:00Here is a list you have seen before: one, four, seven, ten, thirteen. There is a rule that produces it from the position. Three n minus two. Put in four and you get ten, without touching any other term. But the list says something that rule does not. Every term is three more than the one before it. That is a second description, and it is a description of a different thing.

0:28The first says where a term is. The second says what happens next. Written down, it is this: the nth term is the term before it, plus three. Now watch that description fail on its own. Add three each time. Start anywhere you like. Start at one and you get one, four, seven, ten, thirteen. Start at minus five and you get minus five, minus two, one, four, seven. Same step. Different sequence.

1:00Run it from thirteen different starting values and you get thirteen different sequences, every one adding three. So the step alone has not named a sequence. It has named a whole family of them. The starting value is not a preliminary you do before the rule begins. It is part of the rule. Call it the seed, and a step without a seed is only half a description. Those two sequences are not strangers.

1:31One, four and seven turn up in both of them. In fact every value they share sits exactly two places later in the second one. Seven is the third term of one sequence and the fifth term of the other. Fifty-two is the eighteenth term of one and the twentieth of the other. The only values one has that the other has not are the two it starts below zero with: minus five and minus two.

2:00So the seed did not change which numbers appear. It changed where they sit. And a sequence is a value with a position, so that is quite enough to make them two different sequences. Written out properly, a step rule always comes with a condition on n. The nth term is the term before it plus three, for n at least two. That condition is not decoration. Watch what happens without it.

2:31At position one, the rule would ask for the term before the first term. There is no such term, so the rule cannot be asked. That is why the seed is given instead. Now change the step so that it reaches back two terms rather than one. Then positions one and two are both out of reach, and the condition becomes n at least three. Reach back three, and it becomes n at least four.

2:58The number in the condition is not a convention. It is how far back the step reaches, plus one. And that same number is how many seeds you have to be given. One piece of notation trips people more than any other. The symbol t with n minus one underneath does not mean the nth term minus one. It means the term one position earlier. In our list, the fourth term is ten and the term before it is seven.

3:31Ten minus one is nine, and nine is not in the sequence at all. Stepping back one position and subtracting one from a value are different operations. There is exactly one kind of sequence where they agree, and they agree by accident: the one whose step is add one. For every other step in this video they never agree, at any position. Steps do not have to be additions. Take this one: each term is double the term before it, plus three.

4:05Seed it at one, for n at least two. Double one and add three: five. Double five and add three: thirteen. Double thirteen and add three: twenty-nine. One, five, thirteen, twenty-nine. Notice that at no point did we use the position. We used the term standing in front of us, and nothing else. Now the question. Is a hundred and thirty-three a term of that sequence? With a position rule you would write an equation and solve it.

4:40With a step rule there is no equation to write. There is only the walk. So walk. After twenty-nine comes sixty-one. After sixty-one, a hundred and twenty-five. And after a hundred and twenty-five, two hundred and fifty-three. It stepped straight over a hundred and thirty-three without landing on it. The sequence has passed the candidate, so the answer is no. That argument is not free. Passing a value proves you will never reach it only if the sequence is going up and staying up.

5:18Here is one that is not. Start at ten, and each term is the distance from seven of the term before. Ten, three, four, three, four. It passed four and then came back to it. Here is another. Start at five and stay where you are. For sequences like those, walking past a number settles nothing at all. There is also a way to settle it outright, a step beyond this idea.

5:46Add three to every term of that doubling sequence: four, eight, sixteen, thirty-two, sixty-four. Every term is three less than a power of two, and a hundred and thirty-six is not a power of two. So no amount of further walking could ever produce it. Not far enough. Never. Steps can also run away from you. Start at three. Each term is the term before it, multiplied by the number just below it.

6:18Three times two is six. Six times five is thirty. Thirty times twenty-nine is eight hundred and seventy. Eight hundred and seventy times eight hundred and sixty-nine is seven hundred and fifty-six thousand and thirty. The next one is past half a trillion, and we are still only at the sixth term. By that same sixth term, adding three has not yet reached a thousand. The step is using its term twice, and that is what turns arithmetic into an avalanche.

6:54Some patterns are step-shaped by nature, and here is the famous one. The seeds are one and two. After that, each term is the sum of the two before it. Two plus one is three. Three plus two is five. Five plus three is eight. One, two, three, five, eight, thirteen, twenty-one, thirty-four, and then fifty-five and eighty-nine. It was written down in the seventh century by Virahanka, who reached it by counting the ways a line of poetry can be built from short and long syllables.

7:31Gopala studied it around eleven thirty-five, Hemachandra around eleven fifty, and Fibonacci around twelve hundred. You may have met it starting one, one instead of one, two. Both are in circulation. Every term of this one sits one place later in that one, so say which seeds you are using before you compute anything. And notice what is missing here: nobody has offered you a rule that computes the fortieth term from the number forty.

8:06If a step can reach back two, it can reach back three. Seeds one, two and four. After that, each term is the total of the three standing before it. One plus two plus four is seven. Two plus four plus seven is thirteen. Four plus seven plus thirteen is twenty-four, then forty-four, then eighty-one. Three seeds, because the step reaches back three, and the condition is n at least four.

8:36Change any one of those seeds and the whole sequence changes, which is the proof that all three are doing work. As far back as the step reaches, that is how many terms you must be handed. One last warning, and then the choice. Start at one and two, and let each term be one more than the total of everything before it. You get one, two, four, eight, sixteen, thirty-two.

9:04Start at one and two again, and let each term be two more than the total of everything up to two places back. That gives one, two, three, five, eight, thirteen, twenty-one, thirty-four. The same sequence we just met, from a rule of a completely different shape. So a sequence is not the same thing as the rule that happens to produce it. Which leaves the practical question: which description do you want?

9:34Reaching the four hundredth term by stepping costs three hundred and ninety-nine steps. Reaching it from the position costs two operations. But some patterns have no position rule at hand, and for those the step is not the lazy version. It is the definition. A step rule is cheap to state and expensive to use. A position rule is the other way round. Ask what the question is shaped like, and take the description that matches it.