Sequences and ConverganceΒΆ
Recall the definition of a sequence: a sequence of \(X`s is a function from the natural numbers to :math:`X\). Usually, instead of \(f(n)\) it is written as \(a_n\). In this chapter, unless mentioned otherwise, sequences will be sequences in an ordered field.
Let \(a\) and \(b\) real numbers, and \(\epsilon>0\) be a real number (informally, think of it as “small”). If \(x<y+\epsilon\), define it as \(x\) is \(\epsilon\)-almost smaller than \(y\). If \(a\) is \(\epsilon\)-smaller than \(b\) and \(b\) is \(\epsilon\)-smaller than \(a\), then \(a-\epsilon<b<a+\epsilon\), or \(-\epsilon<b-a<\epsilon\).
Definition: In an ordered field, the absolute value \(|x|\) is defined as
Since
and
then
Call this “\(b\) and \(a\) are \(\epsilon\)-close”. Note that since \(|b-a|=|a-b|\), this relationship is symmetric (though not, in general, transitive). An alternative way of saying it is “within \(epsilon\) of each other”. The reason this relationship has no many ways is because this, above all else, defines calculus.
If \(a_n\) and \(b_n\) are sequences, and there exists \(N\) such that for all \(n>N\), \(a_n=b_n\), then they “share a tail”. Sharing a tail is obviously a reflexive and symmetric condition. It is also transitive: if \(a_n\) shares a tail with \(b_n\), starting at \(N\), and \(b_n\) shares a tail with \(c_n\), starting at \(M\), then if \(n>\text{max}{N,M}\), \(a_n=b_n=c_n\), and so \(a_n\) shares a tail with \(c_n\).
A property of sequences is called a tail property if it is the same for sequences sharing a tail.
Here is an example: the property of having all the elements in a sequence bounded from above is a tail property, though it is not immediately obvious that it is.
Lemma: Every finite set has an upper bound
Proof: By induction on the size of the set. If the size is 0, the set is empty and so any number (say, \(1\)) is an upper bound. Assume every set of size \(n\) is bounded. If \(A\) is a set of \(n+1\) elements, let \(x\in A\). \(A-{x}\) is a set of \(n\) elements, so it has an upper bound, \(b\). If \(b\geq x\), then \(b\) is an upper bound for \(A\). Otherwise \(b<x\), and so \(x\) is an upper bound for \(A\). Either way, \(A\) is bounded from above.
Now, if \(a_n\) is a sequence which shares a tail with \(b_n\), and the latter is bounded from above by \(b\), then for \(n>N\), \(a_n=b_n\leq b\). If \(a\) is an upper bound for \({a_1,...,a_{N-1} }\), then \(\text{max}{a,b}\) is an upper bound for all of \(a_n\).
Being bounded from above by a particular number is not, of course, a tail property. It can be explicitly transformed to a tail property by looking only at tails: a sequence \(a_n\) will be said to be “eventually bounded from above” by \(a\) if there exists a \(N\) such that for all \(n>N\), \(a_n\leq a\). It is straightforward to verify that this is a tail property. Similarly, a sequence is defined to be “eventually bounded from below” by \(a\) if there exists a \(N\) such that for all \(n>N\), \(a_n\geq a\).
A sequence, \(a_n\) is eventually \(\epsilon\)-close to \(a\) if it is both eventually bounded from above by \(a+\epsilon\) and eventually bounded from below by \(a-\epsilon\). If \(a_n\) is \(\epsilon\)-close to \(a\) for all \(\epsilon>0\), then \(a_n\) converges to \(a\).
Note that any sequence that converges has a bounded tail, and therefore it is bounded. In other words, an unbounded sequence will not converge to anything.
A sequence is said to be increasing if for all \(n\), \(a_n\leq a_{n+1}\). A sequence is said to be decreasing if for all \(n\), \(a_n\geq a_{n+1}\). A sequence is said to be monotonic if it is either increasing or decreasing.
Theorem: in a complete ordered field, every monotonic sequence converges.
Proof: First assume that \(a_n\) is increasing. Let \(a\) be a least upper bound. Then \(a_n\leq a<a+\epsilon\) for every \(n\) and \(\epsilon\). Since \(a\) is a least upper bound, and \(a-\epsilon<a\), then \(a-\epsilon\) is not an upper bound. So there is a \(N\), \(a-\epsilon<a_N\). If \(n>N\), :math:a-epsilon<a_n<a+epsilon`.
Now if \(a_n\) is decreasing, then :math`-a_n` is increasing and converges to \(a\). Note that \(|-a_n-a|=|a_n-(-a)|\), and so \(a_n\) converges to \(-a\).
QED
Note that this theorem is only true in complete ordered fields.