Sequences and Iteration

Return to Contents

Limits of Sequences

The idea of a limit is one of the seminal new concepts that the Calculus introduced. One of the easiest ways to visualize limits is in terms of sequences of numbers. If the finite set then an indexed variable is a function from (Real numbers). We denote the natural numbers: . A sequence is a function from . It is like an indexed variable except that it does not necessarily terminate. We will denote a sequence a by the open-ended ordered collection of numbers: . The ellipsis at the end means that these numbers go on and on and do not end. An indexed variable may be thought of as a terminated (or a finite) sequence: .

We say that a sequence of numbers converges to a limit if the terms of the sequence get and remain as close as we like to as long as we are far enough along the sequence.

For example, the sequence {0.3, 0.33, 0.333, 0.3333, ...} converges to the limit because we can make the terms get and stay as close as we like to as long as we are patient enough. If we say that and so on, then it is obvious that for any K we choose as long as . That is how long we have to wait.

Now the statement that the sequence converges to a limit is written

In order to make it precise, we must realize that it is a proposition. It says that one can guarantee, for each (positive) number that there is in fact a (natural) number such that the following implication is true:

The statement is just another way to say that the distance from to L is smaller than . The statement

means that one must prove that whenever a number is proposed as a challenge, one can always respond with a natural number N such that the implication is true. It is not a simple statement, but we urge you to reflect on it. We will present many examples of such statements in this book. They always mean the same thing.

The infinite nature of sequences betrays the fact that they are always theoretical objects. They must be defined by a rule if they are to continue indefinitely. So they are always abstract models rather than data collected in experiment, because no experiment can provide an infinite number of measurements.

Now sequences are defined by rules, and these rules can have a variety of forms. For example, we might define a sequence by the rule that where k is a nonnegative integer . Then the odd natural numbers. Such a sequence is given by an explicit rule that tells us how to determine the term from the index alone. We'll call such a rule a function rule for the sequence, and we will call the sequence a function sequence, or an iterative sequence.

Another example of a sequence is the sequence PI = where the ellipsis means that PI(n) is the nth decimal digit of pi counting from the left. This is a function sequence, but the rule does not have a simple algebraic form. Rather it is a prescription for producing the nth term that becomes more and more complex as n becomes larger. The fact that it cannot be reduced to algebraic rule is expressed in the irrationality of pi. The sequence of decimal digits in any rational number can easily be produced by algebraic rule.

For example, the sequence ( 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, ...) for the decimal digits of the fraction 1/7 has an easily recognizable rule: repeat 1, 4, 2, 8, 5, 7 forever.

Now consider the sequence represented by the rule:

So that

and so on. This is also a function sequence although the algebraic rule that defines it becomes more and more complicated. But here we may notice something interesting.

(1.1)

a(1) = 1 and

a(n) = 1/(1+a(n-1)) (if n > 1)

Recursive Sequences

Now this rule that defines it is easy to write down, but it is no longer a function rule or an iterative rule (does not describe the nth term in terms of n alone, but refers also to the term. Equation (1.1) is an example of a recursive definition of a sequence. It is recursive because the definition of the nth term refers to terms in the sequence before the nth. This sequence is therefore called a recursively defined sequence, or simply a recursive sequence. What it really means to say that a sequence is recursive is that there is a relation that expresses the nth term in terms of an invariant rule based on one or more earlier terms of the sequence, those terms being counted from the nth term. We point out two things:

Every sequence is a function sequence, but some function sequences have recursive definitions, and some do not. A recursive definition must "start" by positing the first few values and telling you where to go from there. Recursive definitions often arise in a natural way.

One imagines some process that "only needs to know its present and past states to proceed to the next state." It is a peculiar and interesting form of determinism.

Exploration: Limits of sequences

In this lab, we will look at a few simple iterative sequences, and explain how you may calculate and experiment with them. And in the next lab, we are going to study a variety of recursive sequences, to get familiar with them, because they will arise throughout the rest of this course.

You may define a sequence (actually, an indexed variable) with indices from -99 to 1000 by writing the start and end indices in the fields:

and by writing the definition of the iteration in the field:

Question: Define a function sequence: by entering the definition a(k) := 1/(2^k) from 0 to 50. Iterate, that is, press and you fill 51 terms of your sequence. They will be: Next, change the rule to: a(k) := a(k) + a(k-1) to accumulate these terms. The result will be the sequence of numbers: The resulting series approaches 2. Thinking of this as a sequence, write a function rule for it, and try to prove that it gets and stays as close as we like to 2. That is, write for some function f and show that:

for any >0 there is an N such that | f(k) - 2 | < whenever k > N.

This is what it means to say that the sequence approaches the limit 2. As you can see, the resulting sequence certainly seems to approach 2.

0 : 1
1 : 1.5
2 : 1.75
3 : 1.875
4 : 1.9375
5 : 1.96875
6 : 1.984375
7 : 1.9921875
8 : 1.99609375
9 : 1.998046875
10 : 1.9990234375
11 : 1.99951171875
12 : 1.999755859375
13 : 1.9998779296875
14 : 1.99993896484375
15 : 1.999969482421875
16 : 1.999984741210937
17 : 1.999992370605468
18 : 1.999996185302734
19 : 1.999998092651367
20 : 1.999999046325683
21 : 1.999999523162841
22 : 1.99999976158142
23 : 1.99999988079071
24 : 1.999999940395355
25 : 1.999999970197677
26 : 1.999999985098838
27 : 1.999999992549419
28 : 1.999999996274709
29 : 1.999999998137354
30 : 1.999999999068677
31 : 1.999999999534338
32 : 1.999999999767169
33 : 1.999999999883584
34 : 1.999999999941792
35 : 1.999999999970896
36 : 1.999999999985448
37 : 1.999999999992724
38 : 1.999999999996362
39 : 1.999999999998181
40 : 1.99999999999909
41 : 1.999999999999545
42 : 1.999999999999772
43 : 1.999999999999886
44 : 1.999999999999943
45 : 1.999999999999971
46 : 1.999999999999985
47 : 1.999999999999992
48 : 1.999999999999996
49 : 1.999999999999998
50 : 1.999999999999999

Initially, the terms in the sequence are all 0. You may set them all back to 0 by pressing the button. Using the button assigns values to terms in the sequence in the range [start, end]. And those values remain until you Iterate! again, or Reset.

Suppose for example, you say (You would type this: ) on the range from 1 to 5 with no initial values. You will get 1,2,3,4,5. If now you change the iteration rule to , and iterate again you get 2,3,4,5,6. If you iterate again, you get 3,4,5,6,7 and so on. The point is, the values stay around.

Thus, you can define a sequence like a(k):= (-1)^k/k (alternating harmonic sequence) from, say 1 to 50. Iterate, and you fill 50 terms of your sequence, starting at 1. Next, change the iteration rule to: a(k):= a(k)+a(k-1) to accumulate these terms. The printout will be the partial sums of the series!
If you do 500 terms you get -.693...

You may define in terms of where j is any index (even possibly k), and in terms of any function of k. Defining in terms of future values is intriguing (assuming a sequence has already been defined).

The previous example is a simple case of a recursive sequence. It gives a recursive definition of the integers. Each new integer is 1 + previous integer. We will explore recursive sequences in some detail on the next page.

Now, if the a-sequence has been defined, you may define a b-sequence in terms of a(j), where j depends on k, and in terms of any function of k. If you press then the new values will be printed and reported, but no sequence values will be affected. We will see shortly how you may define a Fibonacci sequence recursively, starting with 1, 1, and then defining a(k) := a(k-1)+a(k-2)... and define as a b-sequence: a(k+1)/a(k) to see convergence to the Golden Ratio.

For the a- or b- sequences, you have the option of showing the graph by checking the box. In this case, the abscissa of the window is set to the number of sequence points. The system then chooses the ordinate so that you can view the entire picture. This is one way to see, for example, a Newton's method iteration, as we will show you later. You may also list the points by checking the: button. You should, in both cases, press clear from time to time because this information will accumulate, and eventually fill some buffer or other.

Finally, you may set the precision, by typing the number of decimal place precision you want in the field:

After that, press Enter. The field does not scroll, but the number you typed is recorded and used thereafter.

Feel free to experiment with iterative sequences on this page. On the next page, we will have a close look at recursive sequences, like the Newton Method iteration.