Sequence Convergence
1 Convergence of Sequences
A sequence \(\{x_n\}\) is an ordered list of numbers indexed by the natural numbers \(\mathbb{N}\) (see Sequences). If \(x_n\in\mathbb{R}\) then we say that \(\{x_n\}\) is a real sequence.
An important property of sequences is convergence. If a sequences converges to some particular value then we say that value is the limit and that the sequence is convergent. A sequence that is not convergent is said to be divergent.
Informally, a sequence \(\{ x_{n} \}\) has a limit \(x\) if the elements of a sequence become arbitrarily close to the limit \(x\) eventually. Clearly, this definition is vague and requires us to specify what we mean by close which in turn requires us to specifically define distance more concretely using a [[metric-spaces.qmd|metric]].
For real numbers \(a,b\in \mathbb{R}\) the Euclidean metric is defined by
\[ d(a,b):=\lvert b-a \rvert. \]
This is a specific type of metric, a function generalizing the concept of distance in sets, studied in Metric Spaces. The most general concept of distance however is that of neighborhoods, which is a concept we study in Topology.
The real sequence \(\{ x_{n} \}\subset \mathbb{R}\) is said to converge to limit \(x \in \mathbb{R}\), written \(x_n\to x\) or \(\lim_{n\to\infty}x_n=x\), if for all \(\epsilon>0\) we can find \(N\) such that for all \(n \geq N\) we have \(\lvert x_{n}-x \rvert<\epsilon\). More succinctly, we write \[ \forall \epsilon>0,\ \exists N\in\mathbb{N} : \forall n \geq N,\ \lvert x_{n}-x \rvert <\epsilon. \]
More generally, a sequence \(\{x_n\}_{n\in\mathbb{N}}\) in a metric space \((X,d)\) is convergent if there exists a limit point \(x\in X\) such that \[ \forall\epsilon>0,\ \exists N\in\mathbb{N},\ \forall n\geq N:\ d(x_n,x)<\epsilon. \]
Proof template for showing \(x_n\to x\):
- Let \(\epsilon>0\) be arbitrary.
- Solve the inequality \(|x_{n}-x|<\epsilon\) to determine how to choose \(N \in \mathbb{N}\) so that it holds for all \(n \geq N\).
- Show that the \(N\) found actually works, namely for all \(n \geq N\).
Define real sequence \(\{ x_{n} \}_{n \in \mathbb{N}}\) by \(x_{n}=\frac{1}{n}\). We show that this sequence converges to \(x=0\) as \(n \to \infty\). Consider arbitrary \(\epsilon>0\). We wish to find \(N\) such that for all \(n\geq N\)
\[ \left\lvert \frac{1}{n} -0\right\rvert <\epsilon \impliedby \frac{1}{n}<\epsilon \impliedby n> \frac{1}{\epsilon}. \]
Thus we can select \(N=\lceil \frac{1}{\epsilon} \rceil+1\) and the proof is complete.
If a sequence \(\{ x_{n} \}\) becomes arbitrarily large as \(n \to \infty\) we write \(\lim_{ n \to \infty }x_{n}=\infty\) and say that the sequence diverges or equivalently, converges to infinity. Similarly if \(\{ x_{n} \}\) becomes arbitrarily negatively large as \(n \to \infty\) we write \(\lim_{ n \to \infty }x_{n}=-\infty\) and say again that the sequence diverges of equivalently, converges to negative infinity.
2 Sequence Limit Results
The limit \(\lim_{ n \to \infty }x_{n}=x\) of a real sequence \(\{ x_{n} \}\) is unique.
Proof. Assume \(x^{(1)}, x^{(2)}\in\mathbb{R}\) are both limits of \(\{ x_{n} \}\) and let \(\epsilon>0\). There exist \(N_1,N_2\) such that \(\lvert x_n-x^{(1)}\rvert<\epsilon/2\) for all \(n\geq N_1\) and \(\lvert x_n-x^{(2)}\rvert<\epsilon/2\) for all \(n\geq N_2\). For \(n\geq\max(N_1,N_2)\) the triangle inequality gives \[ \lvert x^{(1)}-x^{(2)}\rvert\leq\lvert x^{(1)}-x_n\rvert+\lvert x_n-x^{(2)}\rvert<\epsilon. \] Since \(\epsilon>0\) is arbitrary, \(x^{(1)}=x^{(2)}\).
Every convergent sequence is bounded.
Proof. Assume \(x_{n}\to x\) and take \(\epsilon=1\), so there is \(N\) with \(\lvert x_{n}-x\rvert<1\) for all \(n\geq N\). By the triangle inequality, for \(n\geq N\), \[ \lvert x_{n}\rvert= \lvert x_{n}-x+x\rvert\leq\lvert x_{n}-x\rvert+\lvert x\rvert< 1 +\lvert x\rvert. \] Hence \(\lvert x_n\rvert\leq M\) for all \(n\), where \(M=\max(\lvert x_{1}\rvert, \dots, \lvert x_{N-1}\rvert, \lvert x\rvert+1)\).
Assume that \(x_{n}\to x\) where \(x_{n}\neq 0\) for all \(n\) and \(x\neq 0\). Then:
- For every \(\beta>1\) there exists \(N \in \mathbb{N}\) such that \(n>N\implies\lvert x_{n}\rvert\geq \frac{\lvert x\rvert}{\beta}\);
- \(\lim_{ n \to \infty }\frac{1}{x_{n}}= \frac{1}{x}\).
Proof.
- Let \(\epsilon = \frac{(\beta-1)\lvert x\rvert}{\beta}>0\). Since \(x_{n}\to x\) there is \(N\) such that \(\lvert x_{n}-x\rvert<\epsilon\) for all \(n>N\). As \(\lvert x\rvert-\lvert x_{n}\rvert\leq \lvert x_{n}-x\rvert\), we get \[ \lvert x_n\rvert>\lvert x\rvert-\frac{(\beta-1)\lvert x\rvert}{\beta}=\frac{\lvert x\rvert}{\beta}. \]
- Let \(\epsilon>0\). By (1) with \(\beta=2\) there is \(N_{1}\) with \(\frac{1}{\lvert x_{n}\rvert}<\frac{2}{\lvert x\rvert}\) for \(n>N_1\), and there is \(N_{2}\) with \(\lvert x_{n}-x\rvert<\frac{\lvert x\rvert^2\epsilon}{2}\) for \(n>N_{2}\). For \(n>\max(N_{1},N_{2})\), \[ \left\lvert \frac{1}{x_{n}}- \frac{1}{x}\right\rvert=\frac{\lvert x_{n}-x\rvert}{\lvert x\rvert\lvert x_{n}\rvert}<\frac{2\lvert x_{n}-x\rvert}{\lvert x\rvert^2}<\epsilon. \]
Let \(\{ a_{n} \}\) and \(\{ b_{n} \}\) be convergent real sequences. Then the following limits exist:
\(\lim_{ n \to \infty }(a_{n}\pm b_{n})=\lim_{ n \to \infty }a_{n}\pm \lim_{ n \to \infty }b_{n}\),
\(\lim_{ n \to \infty }ca_{n}=c\lim_{ n \to \infty }a_{n}\) for all \(c\in \mathbb{R}\),
\(\lim_{ n \to \infty }(a_{n}b_{n})=\left(\lim_{ n \to \infty }a_{n}\right)\left(\lim_{ n \to \infty }b_{n}\right)\),
\(\lim_{ n \to \infty } \frac{a_{n}}{b_{n}}= \frac{{\lim_{ n \to \infty }a_{n}}}{\lim_{ n \to \infty }b_{n}}\) given that \(\lim_{ n \to \infty }b_{n}\neq 0\) and \(b_n\neq0\) for all \(n\), and
\(\lim_{ n \to \infty }a_{n}^p=(\lim_{ n \to \infty }a_{n})^p\) for all \(p>0\) and \(a_{n}>0\).
Proof. Let \(a_n\to a\) and \(b_n\to b\). (1) Given \(\epsilon>0\) choose \(N\) so that \(\lvert a_n-a\rvert,\lvert b_n-b\rvert<\epsilon/2\) for \(n\geq N\); then \(\lvert (a_n\pm b_n)-(a\pm b)\rvert<\epsilon\). (2) Follows from (3) with the constant sequence \(b_n=c\). (3) We have \[ \lvert a_nb_n-ab\rvert\leq\lvert a_n\rvert\lvert b_n-b\rvert+\lvert b\rvert\lvert a_n-a\rvert\leq M\lvert b_n-b\rvert+\lvert b\rvert\lvert a_n-a\rvert, \] where \(M\) bounds \(\{a_n\}\) by the boundedness theorem, and both terms are made less than \(\epsilon/2\) for \(n\) large. (4) By the reciprocal theorem \(1/b_n\to1/b\), so apply (3) to \(a_n\cdot\frac{1}{b_n}\). (5) is left as an exercise.
For dominated sequence \(x_{n}\leq y_{n}\) for all \(n>N\) then \(\lim_{ n \to \infty }x_{n}\leq \lim_{ n \to \infty }y_{n}\).
PROOF:
For some sequence \(\{ z_{n} \}_{n \in \mathbb{N}}\) such that \(x_{n}\leq z_{n}\leq y_{n}\) for all \(n>N\) and \(\lim_{ n \to \infty }x_{n}=\lim_{ n \to \infty }y_{n}=z\) then \(\{ z_{n} \}\) is convergent and \[ \lim_{ n \to \infty } z_{n}=z. \]
PROOF:
If a sequence is bounded and monotonic then it is convergent.
PROOF:
A sequence is convergent if and only if all of its subsequences are convergent.
PROOF:
3 Cauchy Convergence
When there is no good candidate for the limit, convergence can be shown using only information on pairs of terms: a real sequence converges if and only if it is Cauchy. See Cauchy Sequence. For the limit superior and limit inferior of a sequence, which exist for every sequence, see Limit Supremum & Limit Infimum.
4 Rate of Convergence
The asymptotic error is a measure of the rate of convergence of a sequence. Specifically, given a sequence \(\{ x_{n} \}\) we are able to compute the asymptotic error constant \(\lambda\) which provides information on the differences between the terms of the sequence and the sequence limit \(x\).
If the limit exists and is finite then we can compute the asymptotic error constant \(\lambda\) as \[ \lambda=\lim_{ n \to \infty } \frac{{\lVert x_{n+1}-x \rVert }}{\lVert x_{n}-x \rVert ^p}, \] where \(p\) is the order of convergence.
When \(p=1\) we say that the order of convergence is linear, when \(p=2\) it is quadratic, \(p=3\) cubic etc. More generally when \(0<p<1\) we say it is sublinear and when \(1<p<2\) we say it is superlinear. Intuitively, the order tells you the polynomial rate at which the errors shrink.
Example: Consider the sequences \(\{ x_{n} \}\) and \(\{ y_{n} \}\) defined by \[ x_{n}=5+\frac{1}{2^n}\quad \&\quad y_{n}=5+\frac{1}{2^{2^n-1}}. \] Both converge to \(5\). For \(x_n\) with \(p=1\), \[ \lambda_{x}=\lim_{ n \to \infty } \frac{2^{-(n+1)}}{2^{-n}} = \frac{1}{2}, \] so the order is linear. For \(y_{n}\) with \(p=2\), \[ \lambda_{y}=\lim_{ n \to \infty } \frac{2^{-(2^{n+1}-1)}}{\left(2^{-(2^{n}-1)}\right)^2}=\frac{2^{-2^{n+1}+1}}{2^{-2^{n+1}+2}}=\frac{1}{2}, \] so the order is quadratic.