Overview Of Sequences

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

We need to take a small diversion and talk about sequences. You need to read the diversion about functions - if you've read that then we're OK. If not, go read it now, or at least be prepared to accept a few things and be ready to go back and check up.

So, what is a sequence?

A sequence is just a collection of things in order. There's a first thing, and second thing, a third thing, and so on. We can have finite sequences, but they turn out not to be very interesting (except for a small but significant minority of people). The really interesting things happen with infinite sequences. By that we don't mean sequences where the items are themselves infinite (although that can happen), but we mean sequences that go on forever and never stop.

You can see here that we're using the same term - "Domain" - for the place where the terms in a sequence come from, and where a function takes values to. There's a good reason for that - we'll see what it is a little further down.

Of course, the things in the sequence need to be chosen from some collection. We often talk about a sequence of counting numbers, or a sequence of integers, or a sequence of rationals, and so on, but we assume that there is some (technical term) "domain" from which our things are chosen.

And of course (well, I say of course, it's not obvious to some people) the same thing can turn up more than once in a sequence. Here's a perfectly valid sequence:

• 3, 3, 3, 3, 3, 3, 3, 3, ...

• 4, 4, 4, 4, 4, 4, 4, 4, ...

• 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, ...

• 4, -1/2, 23.7, -pi, telephone, ...

And so on.

So here's a sequence:

• 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, ...

And now here's why I warned you about functions. Let's take a sequence where all the terms (items) are chosen from a set X. Then we can think of the sequence as being a function from the counting numbers into X. To do that we need to define what the function is for each counting number. Here's how:

• For 1, let f(1) be the first term from the sequence.
• For 2, let f(2) be the second term from the sequence.
• For 3, let f(3) be the third term from the sequence.

This works both ways! If you have a function $f:N{\rightarrow}X$ then you have a sequence:

• f(1), f(2), f(3), f(4), ...

• $x_1,~x_2,~x_3,~x_4,~...$

• $f(n)=x_n$

I'm being a bit picky here about the notation, and feel free to skim (but not skip!) this, and come back to it later when it will feel a lot more obvious.

So we are obviously (for some definition of "obviously") at this stage most interested in sequences where all the terms (items) are rational numbers. For convenience we refer to these as "sequences of rationals", which is less of a mouthful than "sequences whose terms are rational numbers."

So let's talk about sequences of rationals (although all of this works for sequences of real numbers).

• A sequence might have an upper bound. That means there might be a number U such that all the terms in the sequence don't exceed U.
• A sequence might have a lower bound. That means that there might be a number L such that no term in the sequence is less than L.
• If a sequence has both an upper bound and a lower bound, then we say the sequence is bounded. In a moment I'll concentrate on bounded sequences.
• In other contexts we might not have a concept of "above" or "below," so a "bounded" sequence is one that never goes outside some sort of limited area. Or volume. or something.

Proof: The proof of this is a typical example of this sort of theorem. We know the original sequence is unbounded, so we just keep taking larger and larger terms from it. In detail ... Let the first term in our new sequence simply be s(1). Any term will do, but there's no reason not to choose that one. So we let s'(1)=s(1). Now suppose that we have chosen the first m terms of s', and consider the last of them, s'(m). Since s' is a subsequence of s, s'(m) has been chosen from s, and so s'(m)=s(k) for some specific k. We are given that s is not bounded above, so s'(m) is not an upper bound. As a consequence, there is some n with k<n such that s(k)=s'(m)<s(n). End of proof

Theorem: If a sequence s of real numbers (or rationals (or integers)) is not bounded above, then there is an infinite subsequence s' that is strictly increasing, which is also unbounded above.

Now you, my patient reader, may feel that the theorem is obvious. In some sense you are right, but in that case I invite you to have a go at proving it without looking at the box at right.

Of course, we haven't actually defined what we mean by a subsequence, but the idea should be pretty clear. Given a sequence s, a subsequence is obtained by using just some of its terms. So we have a sequence:

• $s_1,\;s_2,\;s_3,\;s_4,\;...$

• $n_1\;<\;n_2\;<\;n_3\;<\;n_4\;<\;...$

• $s_{n_1},\;s_{n_2},\;s_{n_3},\;s_{n_4},\;...$

• $s'(k)=s(n_k)$

As an example, consider the sequence:

• 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, ...

• 1, 1, 1, 1, 1, 1, 1, ...
• 1, 2, 3, 4, 5, 6, 7, ...
• 1, 3, 1, 5, 1, 7, 1, ...

• 1, 5, 1, 3, 7, 4, ...
• 4, 4, 4, 4, 4, 4, ...

(To be continued ...)