8 Definitions
Highlights of this Chapter: we define the notion of converges, and discuss examples of how to prove a sequence converges directly from this definition.
Definition 8.1 (Sequence) A sequence is an infinite ordered list of numbers \[(s_1,s_2,s_3,\ldots,s_n,\ldots)\] Each individual element is a term of the sequence, with an subscript (the index) denoting its position in the list.
Most often, we take the set of indices to be \(1,2,3,\ldots\), but any infinite subset of the integers will do. For example, the sequence \(p_n\) of perimeters of inscribed \(n\)-gons starts with index \(3\) (the triangle), as this is the smallest polygon. And, the subsequence Archimedes used to calculate \(\pi\) started with the hexagon and then iterated doubling: \(P_6,P_{12}, P_{24},\ldots\) so has index set \[\{6,12,24,48,96,192,384,\ldots\}\]
Formally, we note all of this is captured using functions, though we will not need this perspective during our day-to-day usage of sequences.
Remark 8.1. Let \(I\subset\ZZ\) be any infinite set of indices. Then a sequence is a function \(s\colon I\to\RR\).
While sequence itself is just an infinite ordered list of numbers, to work with such an object we often require a way to compute its terms. Sometimes this is hard! For example, the sequence
\[\pi_n=\textrm{ the number of prime numbers $\leq n$ }\]
Is called the prime counting function, and being able to compute its exact values efficiently would be monumental progress in number theory. In practice, sequences that we can compute with efficiently are often presented to us in one of two ways:
- Closed Formula For each \(n\), we are given some formula of the type familiar from high school mathematics, and plugging \(n\) into this formula yields the \(n^{th}\) term of the sequence. Some examples are
\[a_n=\frac{n^2+1}{3n-2},\hspace{1cm}b_n=\sin\left(\frac{1}{n}\right)\hspace{1cm}c_n=\sqrt{1+\frac{\sqrt{n}}{n+1}}\]
- Recursive Definition For each \(n\), we are not given a formula to compute \(s_n\) directly, but rather we are given a formula to compute it from the previous value \(s_{n-1}\).
Here’s some example sequences that are important both to us, and the history of analysis:
Example 8.1 (Babylonians and \(\sqrt{2}\)) Starting from rectangle of width and height \(w,h\), the Babylonians created a new rectangle whose width was the average of these, and whose height was whatever is required to keep the area \(2\): \[w_{\mathrm{new}}=\frac{w+h}{2}\hspace{1cm}h_{\mathrm{new}}=\frac{2}{w_{\mathrm{new}}}\]
This because we can solve for \(h\) in terms of \(w\), this induces a recursive sequence for the widths. Starting from some \((w_n,h_n)\) we have
\[w_{n+1}=\frac{w_n+h_n}{2}=\frac{w_n+\frac{2}{w_n}}{2}=\frac{w_n}{2}+\frac{1}{w_n}\]
Thus, in modern terminology the babylonian procedure defines a recursive sequence, given any starting rectangle. If we begin with the rectangle of wdith 2 and height 1, we get
\[w_0=2,\hspace{1cm}w_{n+1}=\frac{w_n}{2}+\frac{1}{w_n}\]
Exercise 8.1 (Babylonians and \(\sqrt{2}\)) Following the same type of reasoning as for width, use the babylonian procedure to produce a recursive formula for the sequence of heights \(h_n\), for a rectangle starting with \(h=1\).
Example 8.2 An infinite sum is a type of recursively defined sequence, built from another sequence called its terms. Assume that \(a_n\) is any sequence. Then we build a sequence \(s_n\) by
\[s_0=a_0\hspace{1cm}s_{n+1}=s_{n-1}+a_n\]
Unpacking this, we see that \(s_1=s_0+a_1=a_0+a_1\), and thus \(s_2=s_1+a_2=a_0+a_1+a_2\) etc.
Exercise 8.2 Come up with a recursive sequence that could be used to formally understand the infinite expression below: \[\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}}}\]
8.1 Convergence
The reason to define a sequence precisely is that we are interested in making rigorous the idea of infinitely many steps, the way the Babylonians may have pictured running their procedure an infinite number of times to produce a perfect square, or Archimedes who ran his side-doubling procedure infinitely many times to produce a circle.
In both cases, there was some number \(L\) out there at infinity that they were probing with a sequence. We call such a number \(L\) the limit of the sequence.
Definition 8.2 (Convergent Sequence) A sequence \(s_n\) converges to a limit \(L\) if for all \(\epsilon>0\) there is some threshold \(N\) past which every further term of the sequence is within \(\epsilon\) of \(L\). Formally, this is the logic expression \[\forall \epsilon >0 \,\exists N\,\forall n>N\,\, |s_n-L|<\epsilon\] When a sequene converges to \(L\) we write \[\lim s_n = L\hspace{1cm}\textrm{or}\hspace{1cm}s_n\to L\]
A sequence is divergent if its not convergent. The definition of convergence formalizes the idea the ancients sought if you keep calculating terms, you’ll get as close as you like to the number you seek
That is, the definition sets up a challenge between you (the computer of the sequence) and the error tolerance. Once you set a certain amount of acceptable error \(\epsilon\), the definition furnishes an \(N\) and guarantees that if you compute the sequence out until \(N\) you’ll be within the tolerated error - and if you keep computing more terms, the approximation will never get worse. Its good to look at some specific examples, while getting comfortable with this:
Exercise 8.3 (Understanding Convergence) Consider the sequence \(a_n=\frac{1}{n^2+13}\). Feel free to use a calculator (even just the google search bar) to experiment and answer these questions.
- What value \(L\) do you think this sequence converges to?
- If \(\epsilon = 1/10\), what value of \(N\) ensures that \(a_n\) is always within \(\epsilon\) of \(L\) for, \(n>N\)?
- If \(\epsilon = 1/100\), what value of \(N\) ensures that \(a_n\) is always within \(\epsilon\) of \(L\) for, \(n>N\)?
Exercise 8.4 (Convergence and \(\sqrt{2}\)) This problem concerns the babylonian sequence for \(\sqrt{2}\) in Example 8.1. Again, use a calculator to play around and answer the following
- For which value of \(N\) are we guaranteed that \(w_n\) calculates the first two decimal places \(\sqrt{2}\) correctly, when \(n>N\)?
- For which value of \(N\) are we guaranteed that \(w_n\) calculates the first eight decimal places \(\sqrt{2}\) correctly, when \(n>N\)?
To prove a sequence converges, we need to work through the string of quantifiers \(\forall \epsilon\exists N\forall n\)… This sets up a sort of imagined battle between an imagined foe setting a value of \(\epsilon\), and you needing to come up with an \(N\) such that you can get the sequene within \(\epsilon\) of the limit.
Here’s one incredibly useful example, that will serve as the basis of many future calculations.
Proposition 8.1 (\(1/n\) converges to \(0\).) Prove that the sequence \(s_n=1/n\) of reciprocals of the natural numbers converges to \(0\).
Proof. Let \(\epsilon>0\). Then set \(N=1/\epsilon\), and choose arbitrary \(n>N\). Since \(n>1/\epsilon\) it follows that \(1/n<\epsilon\), and hence that \[\left|\frac{1}{n}-0\right|<\epsilon\]
Since \(n>N\) was arbitrary, this holds for all such \(n\), and we have proved for this \(\epsilon\), theres an \(N\) with \(n>N\) implying the sequence \(1/n\) is within \(\epsilon\) of the proposed limit \(0\). Since \(\epsilon\) was also arbitrary, we have in fact proved this for all positive epsilon, and thus we conclude \[\frac{1}{n}\to 0\]
Exercise 8.5 (\(\frac{n}{n+1}\) converges to \(1\)) Prove this directly from the limit definition.
Exercise 8.6 (\(\frac{n}{n^2+1}\) converges to \(0\).) Prove this directly from the limit definition.
Example 8.3 (\(\frac{1}{2^n}\to 0\)) Here’s a sketch of an argument: you should fill in the details. Let \(\epsilon>0\). Then we want to find an \(N\) where \(n>N\) implies \(1/2^n<\epsilon\). First, we prove by induction that \(2^n\geq n\) for all \(n\). Thus, \(1/2^n<1/n\), and so it suffices to find \(N\) where \(1/n<\epsilon\). But this is exactly what we did above in the proof that \(1/n\to 0\). So this is possible, and hence \(1/2^n\to 0\).
Exercise 8.7 Give an example of the following, or explain why no such example can exist.
- A sequence with infinitely many terms equal to zero, but does not converge to zero.
- A sequence with infinitely many terms equal to zero, which converges to a nonzero number.
- A sequence of irrational numbers that converges to a rational number.
- A convergent sequence where every term is an integer.
Exercise 8.8 Prove, directly from the definition of convergence, that \[\frac{2n-2}{5n+1}\to \frac{2}{5}\]
8.1.1 Some Useful Limits
We will soon develop several theorems that let us calculate many limits without tediously chasing down an \(N\) for every \(\epsilon\). But there are still several ‘basic limits’ that we will need to know, that will prove useful as building blocks of more complicated limits, as well as foundations to further theory in analysis. We compute several of them here: you should not worry too hard about committing these to memory; but rather read the proofs as examples of how to play the \(\epsilon-N\) game in tricky situations.
This first is useful in developing the theory of geometric series: :::{#exm-an-to-o} Let \(|a|<1\), then the sequence \(a^n\) of repeated powers of \(a\) converges to \(0\). ::: :::{.proof} :::
This next is an essential building block of the theory of exponential functions: :::{#exm-nth-root-n} The sequence \(n^{1/n}\) converges to 1. ::: :::{.proof} :::
8.2 Divergence
The definition of convergence picks out a very nice class of sequences: those that get arbitrarily close to a fixed value, as their index grows. The rest of sequences - anything that does not have this nice property, are all lumped into the category of divergent.
Definition 8.3 (Divergence) A sequence diverges if its not true that for any \(\epsilon\) you can find an \(N\) where beyond that, all terms of the sequence differ from some constant (the limit) less than \(\epsilon\).
Phrasing this positively: a sequence \(a_n\) diverges if for every value of \(a\), there exists some \(\epsilon>0\) where no matter which \(N\) you pick, there’s always some \(n>N\) where \(|a_n-a|>\epsilon\). There’s a lot of quantifiers here! Written out in first order logic:
\[\forall a\in\RR\; \exists \epsilon>0\;\forall N\; \exists n>N\;\; |a_n-a|>\epsilon\]
Again, its easiest to illustrate with an example:
Example 8.4 (\((-1)^n\) Diverges) (Example 3.18, on page 78 of text)
8.2.1 \(\bigstar\) Divergence to \(\infty\)
Definition 8.4 (Diverging to \(\pm\infty\)) A sequence \(s_n\) diverges to \(\infty\) if for all \(M>0\) there exists an threshold past which the sequence is always larger than \(M\). As a logic statement, \[\forall M>0\, \exists N\, \forall n>N\, s_n>M\]
Exercise 8.9 (\(n^2\) diverges to \(\infty\).)
Proposition 8.2 If \(a>1\) then \(a^n\) diverges to infinity.
While we are not often interested in sequences going to infinity themselves, they are a useful tool to prove that other sequences diverge. But they also provide a tool to help prove certain sequences converge
Proposition 8.3 A sequence \(s_n\) of positive terms converges to \(0\) if and only if its reciprocals \(1/s_n\) diverge to \(\infty\).
Proof.
Exercise 8.10
- Give an example of two divergent sequences \(a_n,b_n\) where \(a_n+b_n\) is convergent.
- Give an example of two divergent sequences \(a_n,b_n\) where \(a_nb_n\) is convergent.
8.3 Uniqueness
Theorem 8.1 (Limits are unique) Let \(a_n\) be a convergent sequence. Then there exists a unique \(a\in\RR\) with \(a_n\to a\).
Proof. Proposition 3.19 in the book
The proof of this theorem shows a couple important points that will occur time and again throughout analysis:
- We proved uniqueness by showing that if \(x\) and \(y\) were both limits, then \(x=y\).
- We proved \(x=y\) by showing that for every \(\epsilon>0\) the difference \(|x-y|<\epsilon\).
- We proved \(|x-y|<\epsilon\) by an \(\epsilon/2\) argument:
- We added zero in a clever way: \(|x-y|=|x-a_n+a_n-y|\)
- We used the triangle inequality \(|x-a_n+a_n-y|\leq |x-a_n|+|a_n-y|\)
- We used the fact that \(a_n\to x\) and \(a_n\to y\) to make each of \(|a_n-x|\) and \(|a_n-y|\) less than \(\epsilon/2\).
There’s one more uniqueness-type theorem about limits that’s useful to get a handle on. We just saw that the limit is uniquely determined by the sequence, but we can say something slightly stronger. Its uniquely determined by the end of the sequence: if you throw away the first finitely many terms, it won’t change the limit.
Definition 8.5 A shifted sequence the result of shifting the indices by a constant \(k\), deleting the first \(k\) terms. Precisely, given a sequence \(a_n\) and some \(k\in \NN\), the sequence \(s_n=a_{n+k}\) is the result of shifting \(a\) by \(k\). \[s_{0}=a_{k}, s_{1}=a_{k+1}, s_{2}=a_{k+2},\ldots\]
Proposition 8.4 Shifting a convergent sequence does not change its limit.
Proof (Scratch Work). Assume that \(a_n\) converges to \(a\), and define the sequence \(s_n\) by deleting the first \(k\) terms of \(a_n\), that is, \(s_n=a_{n+k}\). We claim that \(s_n\to a\).
Let \(\epsilon>0\) and choose an \(N\) such that if \(n>N\) we know that \(|a_n-a|<\epsilon\) (we know such an \(N\) exists by the assumption \(a_n\to a\)). Now consider \(|s_n-a|\). Since \(s_n=a_{n+k}\), we know \(|s_n-a|<\epsilon\) because we already knew \(|a_{n+k}-a|<\epsilon\): we knew this for every single index bigger than \(N\).
Thus, for all \(n>N\) we have \(|s_n-a|<\epsilon\), which is the definition of \(s_n\to a\).
This can be generalized, to show that any two sequences which are eventually the same have the same limit. Since the first finite part of any sequence is irrelevant to its limiting behavior, its nice to have a word for “the rest of the sequence, after throwing away an unspecified amount at the beginning”. This is called the tail.
Definition 8.6 (Tail of a Sequence) The tail of a sequence is what remains after chopping off an arbitrary (finite) number of terms from the beginning of the sequence. Two sequences have the same tail if they agree after some point: more precisely, \(a_n\) and \(b_n\) have the same tail if there is an \(N_a\) and \(N_b\) such that for all \(k\in\NN\) \[a_{N_a+k}=b_{N_b+k}\]
Example 8.5 (Tail of a Sequence) The following two sequences have the same tail: \[a_n = 1,1,4,3,1,5,1,3,1,4,7,8,9,10,11,12,13,14,\ldots\] \[b_n = -4,3,9,10,11,12,13,14,15,16,17,18\ldots\]
We can see this because \(a_{13}=b_3=9\), and \(a_{14}=b_4=10\), and \(a_{15}=b_5=11\)…for every \(k\) we have that \(a_{13+k}=b_{3+k}\) so they agree after chopping the first 12 terms off of \(a_n\) and the first two terms off of \(b_n\).
Exercise 8.11 (Convergence only depends on the tail) If two sequences have the same tail, then they either both converge or both diverge, and if they converge, they have the same limit.
8.4 \(\bigstar\) Topology
With an eye to topology, everything about sequences and convergence can be rephrased in terms of open sets, instead of with talk about \(\epsilon\) and inequalities.
Definition 8.7 (Neighborhoods) A neighborhood of a point \(x\) is any open set \(U\) containing \(x\). The \(\epsilon\)-neighborhood of \(x\) is the neighborhood \(U_\epsilon = (x-\epsilon,x+\epsilon)\)
Definition 8.8 (Convergence and \(\epsilon\)-Neighborhoods) A sequence \(a_n\) converges to \(a\) if every \(\epsilon\) neighborhood contains all but finitely many terms of the sequence.
That this is equivalent to Definition 8.2, because the definition of epsilon neighborhood exactly captures the interval discussed in the original definition of convergence.
Exercise 8.12 (Convergence and \(\epsilon\)-Neighborhoods) The definition of convergence in terms of epsilon neighborhoods is equivalent to the usual definition in terms of absolute values and inequalities.
The definition of an epsilon neighborhood makes sense only somewhere like the real line, where we can talk about intervals. So, the general topological definition must dispense with this notion and talk just about open sets:
Definition 8.9 A sequence \(a_n\) converges to \(a\) if every neighborhood contains all but finitely many terms of the sequence.
Exercise 8.13 (Convergence and Neighborhoods) Prove this is equivalent to convergence using \(\epsilon\) neighborhoods. Hint: show that every neighborhood contains some epsilon neighborhood. Can you show that is enough?