Sequences and recurrence relations

What is a sequence?

A *sequence* is just a list, such as , or . The list may be finite, as with . It may be infinite. We may imagine it going on forever as indicated by the three dots in .

When people talk about sequences in general, they often use subscripts: "Suppose we have a sequence , , ,... ." Here is how we can do this for the two examples we just saw.

**Example 1**: is the sequence {, , , , , }, where = , for = 1, 2, 3, 4, 5, 6.

**Example 2**: looks like it could be described as the sequence {, , , ,...}, where = , for = 0, 1, 2, 3, 4,... .

A sequence is a special kind of function**--**a function whose domain is a set of integers. All we do is think of the terms of the sequence as a list of function outputs. That is what the subscript indicates: (or or whatever) is the output, when is the input.

For example, here is a function defined the ordinary way.

This function generates the sequence of example 1 above if we use only integer inputs.

Working with sequences is easy to do with *Mathematica* if we write sequences as functions.

Two ways to describe a sequence

Like a CD

A CD player can instantly play any track. To play the fourth track, you do not have to fast-forward through the first three tracks.

If you have an explicit formula for the general term of a sequence, then you have the equivalent of a CD player. You can instantly get any term of the sequence. To get the 9th term, you do not need to calculate the first eight terms.

Here is an example.

Here is the 4th term.

Here is the term.

Try doing that one by hand.

Like a tape

A tape player cannot instantly play any track on it. To play the fourth track on one side, you have to fast-forward through the first three tracks on that side.

If you have a recurrence relation for the general term of a sequence, then you have the equivalent of a tape player. You can get any term of the sequence, but to get to a later term you need to calculate the other terms that went before.

Here's an example of a recurrence relation.

The last part says: in order to get the next term in the sequence (the one numbered ""), you take the previous term in the sequence (the one numbered "") and add 2 to that.

Notice the two important parts: a starting point and the recipe that tells you what the term is, provided you already know what the term is that went before.

Here are the first few terms of the sequence .

Here is another example of a recurrence relation.

Here are the first few terms of the sequence .

Formally, a *recurrence relation* is a formula which has an element of a sequence as output and used the predecessors of as input. In addition there need to be a starting point (or starting points). In the above examples was always given as starting point. Using a recurrence relation is a standard topic in programming courses in computer science.

Solving a recurrence relation: finding the explicit formula of a sequence from the recurrence relation

Tape players are nice, but the fact is that CD players have several advantages. On a CD player you can get to any track quickly and directly without having to rewind a tape to the right track. In the same way, having an explicit formula for the general term of a sequence has an advantage over just having a recurrence relation. That is why people worry about solving a recurrence relation. That means starting out with a recurrence relation, and then using it to figure out an explicit formula for the general term of the sequence.

Example 1

Sometimes it is easy to see what the general formula is. Recall an earlier example:

There does not seem much doubt that this is the sequence of odd positive integers. But we really cannot be sure without some more checking.

It looks like might be . Invent a new name to avoid confusion.

Now see if they agree.

The two sequences agree. We can even check in general. We cannot just plug in b[k], but we can check to see if bnew[k] satisfies the recurrence relation.

The starting point checks. Now try the recurrence.

*Mathematica* did not decide. Try simplifying.

It checks and now we know that is an explicit formula.

Example 2

Here is another recurrence relation, together with the first few terms of it. Solve it.

Since we are multiplying old terms by 3 (and then add ) to get new terms, we might look at powers of three. Here are those terms again, together with powers of three.

It looks like adding to gives . Let us check some more values to see if that pattern continues.

Adding to continues to give . That says that . How can we be sure that it works for all values of ?

To be sure, we check it out directly. Invent a new name for the sequence.

Now, see if cnew[n] satisfies the recurrence relation, which had two parts: , and .

The starting value is OK, but *Mathematica* isn't sure about the recurrence part. Tell *Mathematica* to look more closely.

It checks and now we know the explicit formula for the recurrence relation.

Example 3

Here is a recurrence relation that is a little more involved.

Here are the first few terms of this sequence.

Not many people would be able to see much of a pattern here, but *Mathematica* has a built-in function RSolve that can solve the recurrence relation.

Note: The command Needs["DiscreteMath`RSolve`"] loads a package in the *Mathematica* kernel that tells *Mathematica* how to do solving of recursions. If you attempt to use the RSolve command without doing Needs["DiscreteMath`RSolve`"], then the RSolve command will not work.

Let us check to see if it really does work.

We check the starting point.

And we check the recurrence.

It's not obviously true to *Mathematica* (and it's certainly not obviously true to many humans). Try simplifying.

It checks and now we know that is an explicit formula.

Summing up sequences

Sometimes we have a sequence and three important questions are, "What happens when we add up the terms? What happens when we add up the first finitely many terms of the sequence? What happens when we add up all the terms of the sequence?"

Looking for a pattern: what do the odd positive integers add up to?

Here is a sequence. The term is what you get when you add up the first odd positive integers.

Notice that the input for the function is . The letter is just a variable used to keep track of counting. The final result does not depend on .

Here are the first few terms of the sequence.

Very surprising! It looks like we get the perfect squares.

Do we always get perfect squares when we add up consecutive odd positive integers? Let's* *see if *Mathematica* can evaluate the sum symbolically--that is, in general, not just for . Here it is again.

*Mathematica* evaluated the sum symbolically and now we know that .

What is a geometric sequence?

A geometric sequence is a sequence in which each term is of the form ,

where and are constants. The key idea is that the ratio of consecutive terms remains constant.

Here are some examples.

Here are some of the terms of the sequences.

Here are the ratios of consecutive terms.

Replay:

Invent your own geometric sequences and take a look at the first few terms. What do you need to do to 1 term of the sequence in order to get the next term of the sequence?

So what is that ratio in general? In general, if the terms of the geometric sequence look like , then the ratio of consecutive terms is just the number .

There it is. The ratio of consecutive terms is just the number . Notice that this also says that in order to get the next term in the sequence from the one you have, you multiply the one you have by that ratio.

Partial sums of geometric sequences

Here is what we had in the previous examples.

Here are the sums (of the terms from 1 to ).

Let's see what happens when *Mathematica* simplifies this.

Can you see a pattern in these answers? If not, try some more examples.

The general term of a geometric sequence looks like , where and are constants. What happens if we ask *Mathematica* to evaluate the partial sums?

We got a complicated formula, but that is what it turns out to be.

What choices of , , or make this undefined?

Answer: Any choice of and will be fine. However causes a division by zero. That makes sense, because for there is a very simple answer. If then and and .