## Sequences

The remainder of the course is a look at discrete calculus, which is a study of all the previous sections (functions, derivatives, integrals) applied to a different kind of function: sequences. A sequence is a function, but instead of taking any real number as input, a sequence takes an integer as input.

## Sequence

A *sequence* is a function from the non-negative integers to the real numbers . The usual functional notation is sometimes replaced with . There are several ways to define a sequence. Here are three of the most common ways, demonstrated on the powers of 2.

- An
*explicit formula*gives as a function of , i.e. . This is usually the most convenient, since it typically gives the most information about the sequence. e.g. for . - A
*recursion relation*gives as a function of previous terms in the sequence. Note that some initial conditions must be given as well. . e.g. ; . - Finally,
*listing terms*can be used if no explicit or recursive formula is available. This is sometimes used in experimental settings so that one can study the terms and look for a pattern. e.g. .

**Example**

Write out the first six terms of the sequence defined by ; . Look for a pattern to try to find an explicit formula for .

One might notice that adding 1 to each term in the sequence gives the sequence , which look like the powers of 2. So it appears that for .

## Limits of sequences

Recall that limits of functions came in two flavors. First, there were limits of the form . The second type of limits were of the form .

Only the second type of limit is sensible for a sequence. (To see why the first type of limit does not make sense for sequences, go back to the definition of a limit.) The definition of for sequences is the same as for continuous functions:

The Limit of a Sequence

We say that

if for any there exists such that for all ,

In other words, the sequence has limit if gets arbitrarily close to for sufficiently large . If the limit exists, then the sequence is said to *converge* to .

Intuitively, a sequence has a limit if for any band around , there is some point where all the terms of are within the band around :

Recall that Newton's method defined a sequence of numbers defined by the recursion relation

Here, the sequence *hopefully* converged to a root of the function . This gives an example of an application where it is useful to know about the convergence of a sequence.

**Example**

Let . Find , if the limit exists. If the limit does not exist, explain why.

We claim the limit is 4. We know that

Therefore, for any we can choose so that . Then for any , we have

as desired. For this course, we will not typically be this formal, but it is useful to see this type of argument at least a few times.

**Example**

Let . Find , if the limit exists. If the limit does not exist, explain why.

From the intuitive understanding of a limit, it is clear that the terms of this sequence are not getting closer together, and so the limit does not exist.

More formally, suppose the limit, say , existed. Then from the definition of the limit of a sequence, we could find a number such that

for all . Since the terms of the sequence are and , this would imply

This implies

Similarly,

which implies by similar algebra that

Since cannot be simultaneously positive and negative, we have reached a contradiction. And so we see that the limit cannot exist.

## Methods for computing limits

Many of the methods for computing limits of continuous functions carry over to computing limits of sequences. In particular, all of the big-O notation still applies.

**Example**

Compute the limit of the sequence .

A little factoring from the radical, and using the binomial series gives

So the limit is .

## Monotone, bounded sequences

In general, it can be difficult to find the limit of a sequence, but for certain sequences it is possible to prove that the limit exists.

A sequence is *monotone increasing* if it is non-decreasing, i.e., . A sequence is *monotone decreasing* if it is non-increasing, i.e., . A sequence that is either monotone increasing or monotone decreasing is *monotone*.

A sequence is *bounded above* if there exists some real number such that for all . Similarly, a sequence is *bounded below* if there exists a real number such that for all . A sequence is *bounded* if it is both bounded above and bounded below.

Monotone Convergence Theorem

If a sequence is bounded and monotone, then the sequence converges.

**Example**

Let be the sequence defined by ; . Show that the sequence converges by using the Monotone Convergence Theorem.

It is not obvious that this sequence is either bounded or monotone. Writing out the first few terms, though, gives . It appears that the sequence is increasing, and that for all .

To show that the sequence is increasing, use induction. The first few terms are increasing, so assume that for some . Then adding 5 and dividing by 2 throughout gives , which implies by the recursive definition of . Thus, the sequence is increasing.

To see that , again use induction. Assume for some . Then adding 5 and dividing by 2 gives . This means by the definition of . Thus, for all . Finally, note that any increasing sequence is bounded below. So the sequence is bounded.

Thus, by the Monotone Convergence Theorem, the sequence converges.

## Recursion relations and limits

When a sequence is defined by a recursion relation and the limit of the sequence exists, one can find the limit by simply taking the limit of both sides of the recursion relation and solving. This is best demonstrated by example.

**Example**

Find the limit , where ; , as in the previous example.

The limit exists by the previous example, so taking limits of both sides of the recursion relation and simplifying gives

(Note that because the limit of a sequence does not depend on the indexing of the terms.) Now, solving for gives , so .

**Example**

Find

by expressing as a limit of a recursively defined sequence which begins . Assume that the limit exists.

The sequence can be defined recursively by ; . Then taking limits of both sides gives . Multiplying through and collecting terms gives , and solving for gives .

Note though that for all , so it must be that . This is the celebrated *golden ratio*.

**Example**

Find . Assume the limit exists.

One can express this as the limit of a recursively defined sequence given by and . Then letting , and taking limits of the recursion relation gives

Squaring both sides and collecting terms gives , which is the same equation from the previous example. Thus, the limit is again the golden ratio .

The golden ratio, often denoted

appears in many settings, both man made and natural. The golden ratio is also deeply connected with the Fibonacci numbers, as we will see in this example and in the future.

**Example**

The *Fibonacci sequence*, is defined by the recursion relation and initial conditions

So the first few Fibonacci numbers are

Show that

You may assume that the limit of the sequence exists. Hint: Observe that

Let

Then, beginning with the hint and taking the limit of both sides, we have

But this means

which is an equation which we solved in an above example, where we found

as desired.

## EXERCISES

- Compute the limit of the sequence .