A simple and intuitive idea provides the foundation for our understanding of sequences: a sequence is just a list of numbers. The numbers on the list are called the terms of the sequence, and most often we are interested in sequences only when their terms elicit some pattern. When such a pattern exists, the sequence is said to be defined by a rule. To make these ideas clearer, let us consider a real-live sequence:
We can see that this is just a list of numbers. We also see that a pattern exists between the terms. Expressing the pattern as a rule, and doing so in plain English, we could say that to get from one member of the sequence to the next, we just add 3.
Sequences can be either finite or infinite in length. The sequence above is infinite - we can keep adding 3 to find successive terms to our hearts' content. A finite sequence, on the other hand, is made up of finitely many terms.
In order to write sequences down more succinctly, we employ the concept of a general term. The general term of a sequence is usually written as a variable with a subscript, for example xn, where x1 is the first term, x2 is the second term, x3 is the third term, and so on. So for the sequence above, x1 = 4, x2 = 7, x3 = 10, etc. We often relate a general term to the sequence's rule with an equation, usually writing xn as a formula in terms of n. For the sequence above we have
So, for the first term, x1, we have n = 1, so that x1 = 3(1) + 1 = 4. Looking above, we see that the first term is indeed 4. The second term? We have x2 = 3(2) + 1 = 7, which matches the sequence.
We often visualize a sequence using a table, like this
The table can sometimes help us see the pattern between n and xn more clearly.
Looking back at our example sequence, consider again the rule that defines its terms. To get from the first term to the second, we add 3 to the first. To get from the second term to the third, we add 3 to the second. In general, to get from the nth term to the succeeding term, we add 3 to the nth term. When one term is somehow determined by those that precede it, as it is in this case, then something called recursion is going on. A formula that expresses recursion is called a recursive formula. Here is an example for the sequence we've been working with so far:
What does this mean? It means that if we want to find xn, we first look at the previous term xn-1 and then add 3 to it. Any time you see a formula for a general term that is defined with previous terms like this, then you're looking at a recursive formula.
Recursive formulas have the advantage of providing a recipe for any term in the sequence, just so long as we already know the terms that came before it. The downside is that finding all the terms leading up to the term that we're interested can take a long time.
Using the above recursive formula we can generate the whole sequence:
x1 = 4
x2 = x1 + 3 = 4 + 3 = 7
x3 = x2 + 3 = 7 + 3 = 10
x4 = x3 + 3 = 10 + 3 = 13
...
It seems like using a recursive formula is tedious. Why not just use the regular formula xn = 3n + 1 instead? For the example we've been working with so far, the regular formula probably is the best way to find a particular term in the sequence. There are some sequences, however, for which a recursive formula may be a simpler. An example is the famous Fibonacci sequence. Here is what it looks like:
How might we write a general term for this sequence? Writing the nth term as a function of n may not be so easy (it does so happen that there is a way to find the nth Fibonacci number as a function of n, but the process for deriving the formula is beyond the scope of this lesson). So what do we do? Well, notice this relationship between the terms:
If we call the general term fn, then we see that it is a sum of the two preceding terms. In the graphic above, the third term, f3 = 2, which is the sum of f1 = 1 and f2 = 1. Likewise, the sixth term f6 = 8, and it is a sum of the terms f5=5 and f4 = 3. Here is a recursive formula! The general term can be written like this:
Using this formula, can we find the eighth Fibonacci number, f8? Of course! Letting n=8, we have f8 = f7 + f6. Looking at the sixth and seventh terms in the above sequence, we see that f7 = 13 and f6 = 8 so that f8 = 13 + 8 = 21. We can now find successive elements of the sequence into infinity.
A recursive formula is just a way to express the idea that one term in a sequence is determined by the some of the terms that precede it. Usually when we write a recursive formula, we will also define the initial terms of the sequence. We have already seen two examples using initial terms; one, when we set x1 = 1 in our first example; and another, when we set the first two Fibonacci numbers f1=1 and f2=1. Once the initial terms were known, the recursive formula could be used to generate the rest of the sequence one term at a time.
We are about to see a few more examples of sequences, but first we introduce the concept of factorials. Let n be any natural number, then the factorial of n, written n!, is the product of n and all the natural numbers that come before it. For example, when n is 5, then we have
In general,
Also, by convention we define 0! = 1.
Using what we have just learned about recursive formulas, we can see that n! admits a recursive definition. Letting our initial term be f1 = 1, we can define the general term as fn = n • fn-1. How does this work? Here is an example to make it clearer. Let n=5. Then f5 = 5!, and 5! = 5 • (4 • 3 • 2 • 1) = 5 • 4! = 5 • f4. The nth factorial number is just n times the factorial that precedes it - recursion strikes again! None of this is necessary for the rest of the lesson, but it is a good example of recursive definitions, and is worth understanding.
Example 1
Let the general term of our sequence be defined by xn = (n+2)/n! What is the fourth term of this sequence? We can find it by setting n=4, and plugging it in to the formula: x4 = (4+2)/4! = 6/(4 • 3 • 2 • 1) = 6/24 = 1/4.
Example 2
Now let the general term be defined xn = n! - 1. What are the first five terms of this sequence?
x1 = 1! - 1 = 1 - 1 = 0
x2 = 2! - 1 = (2 • 1) - 1 = 1
x3 = 3! - 1 = (3 • 2 • 1) -1 = 6 - 1 = 5
x4 = 4! - 1 = (4 • 3 • 2 • 1) - 1 = 24 - 1 = 23
x5 = 5! - 1 = (5 • 4 • 3 • 2 • 1) - 1 = 120 - 1 = 119
