8.6: Real Sequences
- Page ID
- 99103
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Recall that a sequence is a function with domain \(\mathbb{N}\) (or \(\mathbb{N}^{+}\)). A real sequence is a real-valued sequence (that is, the range of the sequence is a subset of the real numbers).
DEFINITION. Subsequence Let \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a sequence and \(f \in \mathbb{N}^{\mathbb{N}}\) be a strictly increasing sequence of natural numbers. Then \[\left\langle a_{f(n)} \mid n \in \mathbb{N}\right\rangle\] is a subsequence of \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\).
EXAMPLE 8.4. Let \(s\) be the sequence \[\langle 2 n \mid n \in \mathbb{N}\rangle=\langle 0,2,4,6,8, \ldots\rangle .\] Then the sequence \(t\) given by \[\langle 6 n \mid n \in \mathbb{N}\rangle=\langle 0,6,12,18, \ldots\rangle\] is a subsequence of \(s\). In this example, \(f(n)=3 n\) is the function that demonstrates that \(t\) is a subsequence of \(s\). Another subsequence of \(s\) is the sequence \[\left\langle 2^{5 n+3} \mid n \in \mathbb{N}\right\rangle\] Recall that a sequence \(\left\langle a_{n}\right\rangle\) is called non-decreasing if \(a_{n+1} \geq a_{n}\) for all \(n\). It is called non-increasing if the inequality is reversed. Everything that is true for a non-decreasing sequence is true, with inequalities reversed, for non-increasing sequences (why?), so rather than state everything twice, we can use the word monotonic to mean a sequence that is either non-increasing (everywhere) or non-decreasing.
LEMMA 8.5. Every non-decreasing real sequence \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) that is bounded above converges to its least upper bound. Every non-increasing real sequence that is bounded below converges to its greatest lower bound.
Proof. We shall only prove the first assertion. Let \(M\) be the least upper bound of \(\left\langle a_{n}\right\rangle\). Let \(\varepsilon>0\). Since \(M\) is the least upper bound, there is \(N \in \mathbb{N}\) such that, \[0<M-a_{N}<\varepsilon .\] Since the sequence is non-decreasing, \[(\forall n \geq N) 0<M-a_{n}<\varepsilon .\] Therefore \(M\) is the limit of the sequence, as desired.
THEOREM 8.6. Bolzano-Weierstrass Theorem Let \([b, c]\) be a closed bounded interval of real numbers and \(s=\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a sequence of real numbers such that \[(\forall n \in \mathbb{N}) a_{n} \in[b, c] .\] Then \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) has a convergent subsequence with limit in \([b, c]\). Discussion. We consider a nested sequence of intervals, all of which contain infinitely many elements of the range of the sequence \(s\), with the radius of the intervals approaching 0 . We construct a subsequence of \(s\) by sequentially selecting elements in the intersection of the range of \(s\) and the successive intervals. We then show that the subsequence we construct is convergent.
PROOF. We prove the theorem for the closed unit interval \([0,1]\). It is straightforward to generalize this argument to arbitrary closed bounded intervals.
If the range of the sequence is a finite set, then at least one element of the range, \(a_{n}\), must have an infinite pre-image. The pre-image of \(a_{n}\) gives a subsequence that converges to \(a_{n}\). Therefore we assume that the range of the sequence is infinite. Let \(S\) be the range of the sequence \(\left\langle a_{n}\right\rangle\).
We define a nested sequence of closed intervals, \(I_{n}=\left\langle\left[b_{n}, c_{n}\right]\right| n \in\) \(\mathbb{N}\rangle\) satisfying
(1) \(I_{0}=[0,1]\)
(2) For all \(n \in \mathbb{N}, I_{n+1} \subset I_{n}\)
(3) \(c_{n}-b_{n}=\frac{1}{2^{n}}\)
(4) For all \(n \in \mathbb{N}, I_{n} \cap S\) is infinite.
Let \(I_{0}=[0,1]\). Assume that we have \(I_{n}\) satisfying the conditions above. At least one of the intervals \(\left[b_{n}, b_{n}+\frac{1}{2^{n+1}}\right]\) and \(\left[b_{n}+\frac{1}{2^{n+1}}, c_{n}\right]\) must contain infinitely many elements of \(S\). Let \(I_{n+1}=\left[b_{n}, b_{n}+\frac{1}{2^{n+1}}\right]\) if the intersection of this set with \(S\) is infinite; otherwise let \(I_{n+1}=\) \(\left[b_{n}+\frac{1}{2^{n+1}}, c_{n}\right]\). Then \(I_{n+1}\) satisfies the conditions above.
The sequence of left end-points of the intervals \(I_{n},\left\langle b_{n} \mid n \in \mathbb{N}\right\rangle\) is non-decreasing. The sequence of right endpoints of the intervals \(I_{n}\), \(\left\langle c_{n} \mid n \in \mathbb{N}\right\rangle\) is non-increasing. Furthermore, for any \(m, n \in \mathbb{N}\), \[b_{m}<c_{n} .\] The set \(\left\{b_{n} \mid n \in \mathbb{N}\right\}\) is bounded above, so by the Least Upper Bound Property the set has a least upper bound, \(\beta\). Similarly the set \(\left\{c_{n} \mid\right.\) \(n \in \mathbb{N}\}\) has a greatest lower bound \(\gamma\). By Lemma \(8.5\) \[\begin{aligned} &\lim _{n \rightarrow \infty} b_{n}=\beta \\ &\lim _{n \rightarrow \infty} c_{n}=\gamma . \end{aligned}\] By the triangle inequality, for any \(n \in \mathbb{N}\), \[|\beta-\gamma| \leq\left|\beta-b_{n}\right|+\left|b_{n}-c_{n}\right|+\left|c_{n}-\gamma\right| .\] All three terms on the right hand side of the inequality tend to 0 as \(n\) approaches infinity, so for any \(\varepsilon>0\), \[|\beta-\gamma|<\varepsilon .\] Hence \(\beta=\gamma\).
We now want to define a subsequence that converges to \(\beta\), by choosing a point in each interval \(I_{n}\) in turn. Formally we do this by defining \(f \in \mathbb{N}^{\mathbb{N}}\) recursively by \[f(0)=0\] and \(f(n+1)\) is the least \(k \in \mathbb{N}\) such that \[[k>f(n)] \wedge\left[a_{k} \in I_{n+1}\right] .\] This is well-defined since \(S \cap I_{n+1}\) is infinite. Then the sequence \(\left\langle a_{f(n)}\right|\) \(n \in \mathbb{N}\rangle\) converges to \(\beta\). To see this, let \(\varepsilon>0\). For any \(n \in \mathbb{N}\) such that \(\frac{1}{2^{n}}<\varepsilon\), \[\left|\beta-a_{f(n)}\right|<c_{n}-b_{n}=\frac{1}{2^{n}}<\varepsilon .\] Therefore \(\left\langle a_{f(n)} \mid n \in \mathbb{N}\right\rangle\) is a convergent subsequence converging to \(\beta\).
DEFINITION. Cauchy sequence Let \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a sequence. The sequence \(\left\langle a_{n}\right\rangle\) is a Cauchy sequence if \[(\forall \varepsilon>0)(\exists N \in \mathbb{N})(\forall m, n \in \mathbb{N})[m, n \geq N] \Rightarrow\left[\left|a_{m}-a_{n}\right|<\varepsilon\right] .\] THEOREM 8.7. A real sequence converges iff it is a Cauchy sequence. PROOF. \(\Rightarrow\)
Let \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a sequence of real numbers that converges to \(a \in \mathbb{R}\).
Let \(\varepsilon>0\) and \(N \in \mathbb{N}\) be such that \[(\forall n \geq N)\left|a-a_{n}\right|<\frac{\varepsilon}{2} .\] Then for any \(m, n \geq N\), \[\left|a_{n}-a_{m}\right| \leq\left|a_{n}-a\right|+\left|a-a_{m}\right|<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon .\] Therefore \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) is a Cauchy sequence.
\(\Leftarrow\)
Let \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) be a Cauchy sequence. Then \[(\exists N \in \mathbb{N})(\forall m, n>N)\left|a_{n}-a_{m}\right|<1 .\] Every term in the sequence after the \(N^{\text {th }}\) term is in the \(\varepsilon\)-neighborhood of \(a_{N}\). So \[(\forall n \geq N) a_{n} \in\left[a_{N}-1, a_{N}+1\right] .\] The sequence \(\left\langle a_{n} \mid n \geq N\right\rangle\) satisfies the hypotheses of the BolzanoWeierstrass Theorem, and thus has a convergent subsequence.
Let \(\left\langle a_{f(n)} \mid n \in \mathbb{N}\right\rangle\) be a convergent subsequence of \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) converging to \(a \in \mathbb{R}\). Let \(\varepsilon>0\). Since \(\left\langle a_{n}\right\rangle\) is Cauchy, there is \(N_{1}\) such that \[\left(\forall m, n \geq N_{1}\right)\left|a_{m}-a_{n}\right|<\frac{\varepsilon}{2} .\] Furthermore, there is \(N_{2} \in \mathbb{N}\) such that \[\left(\forall n \geq N_{2}\right)\left|a_{f(n)}-a\right|<\frac{\varepsilon}{2} .\] Let \(N_{3} \geq N_{1}, f\left(N_{2}\right)\). Then \(N_{3} \geq N_{2}\) and \[\left(\forall n \geq N_{3}\right)\left|a_{n}-a\right| \leq\left|a_{n}-a_{f(n)}\right|+\left|a_{f(n)}-a\right|<\varepsilon .\] Therefore the sequence \(\left\langle a_{n} \mid n \in \mathbb{N}\right\rangle\) converges to \(a\).
Cauchy sequences get at the essence of the order-completeness of the real numbers. A Cauchy sequence of rational numbers need not converge to a rational number. For instance, let \(a\) be any irrational number, and let \(a_{n}\) be the decimal approximation of \(a\) to the \(n^{\text {th }}\) digit. The sequence \(\left\langle a_{n}\right\rangle\) is a Cauchy sequence of rational numbers that converges to an irrational number. However if a Cauchy sequence fails to converge in a set of numbers, it is reasonable to say that there is a gap in the set of numbers. The real numbers are defined so that these gaps are filled.