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 
.
