Editing OverviewOfSequences
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Apr 18 19:21:36 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
Diversion: Sequences 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. [[[>50 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, ... And there was no particular reason for choosing 3. Here's another sequence: * 4, 4, 4, 4, 4, 4, 4, 4, ... We don't need to have just one value: * 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, ... And they don't have to be whole numbers, and they don't have to be positive, and they don't have to be numbers: * 4, -1/2, 23.7, -pi, telephone, ... In this last example it's hard to see if there's a rule to define or predict the next term in the sequence, and in general there may not be. In some cases you may think there's a rule, but there isn't. In some cases there may be a rule, but you can't ~work it out. And so on. So here's a sequence: * 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, ... You probably can ~work out what the rule is for that one. 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. You can see where this is going. For /n/ we define /f(n)/ to be the EQN:n^{th} term from the sequence. This ~works both ways! If you have a function EQN:f:N{\rightarrow}X then you have a sequence: * !/ f(1), f(2), f(3), f(4), ... !/ So if we have a sequence: * EQN:x_1,~x_2,~x_3,~x_4,~... we also have a function f: * EQN:f(n)=x_n We slide between the notations as we see fit, using the most convenient notation for the moment, talking about EQN:x_n one moment, and /f(n)/ the next. [[[>50 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. If a sequence is not bounded above, that means that no matter how high you go, there will eventually be a term of the sequence that's bigger. This has an interesting consequence. [[[>50 !* 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: * EQN:s_1,\;s_2,\;s_3,\;s_4,\;... We pick an increasing sequence of natural numbers: * EQN:n_1\;<\;n_2\;<\;n_3\;<\;n_4\;<\;... and we look at only those terms from /s,/ so we get the terms: * EQN:s_{n_1},\;s_{n_2},\;s_{n_3},\;s_{n_4},\;... In other words: * EQN:s'(k)=s(n_k) Note here that we have freely mixed the function and the subscript notations. As an example, consider the sequence: * 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, ... We can pick the following sub-sequences: * 1, 1, 1, 1, 1, 1, 1, ... * 1, 2, 3, 4, 5, 6, 7, ... * 1, 3, 1, 5, 1, 7, 1, ... We may not, however, choose the terms out of order, nor may we repeat terms. These is not allowed: * 1, 5, 1, 3, 7, 4, ... * 4, 4, 4, 4, 4, 4, ... ---- (To be continued ...)