%MIT OpenCourseWare: https://ocw.mit.edu
%18.100A / 18.1001 Real Analysis, Fall 2020
%License: Creative Commons BY-NC-SA 
%For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.

%\subsection*{Lecture 7:}
%\textbf{\underline{Convergent Sequences of the Real Numbers}}

\noindent We will do another example of limits that converge:
\begin{example}
$\lim_{n\to \infty} \frac{1}{n^2 + 2n + 100}=0.$
\end{example}
\begin{proof}
Let $\epsilon>0$ and choose $M\in \NN$ such that $M> \frac{\epsilon^{-1}}{2}$. Then, $\forall n \geq M$,
\[
\left|\frac{1}{n^2 +2m +100} -0\right| \leq \frac{1}{n^2 +2m +100} \leq \frac{1}{2n} \leq \frac{1}{2M} < \epsilon.
\]
\end{proof}

The fact that we can go from a complicated rational function to one that works for our purposes (namely to prove the sequence converges to 0) is \textit{awesome}. 

\begin{example}
Consider the sequence $x_n = (-1)^n$. This sequence is divergent.
\end{example}
\begin{proof}
Let $x\in \RR$. We claim $\lim_{n\to \infty} (-1)^n \neq x$. To prove this, we simply need find \textit{an} epsilon that stops the sequence from converging. For instance, consider $\epsilon_0 = \frac{1}{2}$. Then, for $M\in \NN$,
\[
1 = |(-1)^M - (-1)^{M+1}| \leq |(-1)^M -x|+|(-1)^{M+1}-x|.
\]
Thus, either $|(-1)^M-x|\geq \frac{1}{2}$ or $|(-1)^{M+1}-x|\geq \frac{1}{2}$. In either case, this shows that the limit cannot converge to $x$.
\end{proof}

\begin{theorem}
If $\{x_n\}$ is convergent, then $\{x_n\}$ is bounded.
\end{theorem}
Before we start the proof, let's first talk about the idea of the proof. Let $\epsilon = 1$ such that $|x_n-x|<1$ for all $n\leq M$ for some $M\in \NN$. Then, there are finitely many elements not in the interval $(x-1,x+1)$. We use this to our advantage.

\textbf{Proof}: Suppose that $\lim_{n\to \infty}x_n = x$. Thus, there exists an $M\in\NN$ such that $|x_n-x|<1$ for all $n\geq M$. Let 
\[
B = \max\{|x_1|, |x_2|,\dots, |x_{M-1}|, |x|+1\}.
\]
If $n <M$, then $|x_n| \leq B$ by construction. If $n\geq M$, then \[
|x_n| \leq |x_n-x| + |x| <1+|x| \leq B.
\] \qed 

\begin{definition}[Monotone]
A sequence $\{x_n\}$ is \vocab{monotone increasing} if $\forall n\in \NN$, $x_{n}\leq x_{n+1}$. A sequence $\{x_n\}$ is \vocab{monotone decreasing} if $\forall n\in \NN$, $x_n \geq x_{n+1}$. If $\{x_n\}$ is either monotone increasing or monotone decreasing, we say $\{x_n\}$ is \vocab{monotone} or \textbf{monotonic.}
\end{definition}

\begin{example}
For example, $x_n =\frac{1}{n}$ is monotone, $y_n = -\frac{1}{n}$ is monotone increasing, and $(-1)^n$ is neither.
\end{example}

\begin{theorem}
Let $\{x_n\}$ be a monotone increasing sequence. Then, $\{x_n\}$ is convergent if and only if $\{x_n\}$ is bounded. Moreover, $\lim_{n\to \infty}x_n = \sup\{x_n \mid n\in \NN\}.$
\end{theorem}
\textbf{Proof}: Firstly, we know that if $\{x_n\}$ is convergent then it is bounded by the previous theorem, Now assume that $\{x_n\}$ is bounded. Then, $x:= \sup\{x_n \mid n\in \NN\}$ exists in $\RR$ by the lowest upper bound property of $\RR$. We now prove that 
\[
\lim_{n\to \infty}x_n = x.
\]
Let $\epsilon>0$. Then, $\exists M_0\in \NN$ such that 
\[
x-\epsilon < x_{M_0}<x
\]
since $x$ is the supremum of the set. Let $M = M_0$. Then, $\forall n\geq M$, we have 
\[
x-\epsilon < x_{M_0} = x_M \leq x_n \leq x < x+\epsilon.
\]
Therefore, $|x_n|< |x+\epsilon|$. Therefore, $x_n \to x$. \qed 

\begin{theorem}
Let $\{x_n\}$ be a monotone decreasing function. Then, $\{x_n\}$ is convergent if and only if $\{x_n\}$ is bounded. Moreover, 
\[
\lim_{n\to \infty} x_n = \inf\{x_n \mid n\in \NN\} 
\]
\end{theorem}
The proof of this is similar to the previous theorem and is thus omitted.

\begin{definition}[Subsequence]
Informally, a subsequence is a sequence with entries coming from another given sequence. In other words, let $\{x_n\}$ be a sequence and let $\{n_k\}$ be a strictly increasing sequence of natural numbers. Then the sequence 
\[
\{x_{n_k}\}_{k=1}^\infty
\]
is called a \vocab{subsequence} of $\{x_n\}$.
\end{definition}

Consider the sequence $\{x_n\} = n$ -- in other words, the sequence $1,2,3,4,\dots$. Then, the following are subsequences of $x_n:$
\begin{align*}
    &1,3,5,7,9,11,\dots \\
    &2,4,6,8,10,\dots \\
    &2,3,5,7,11,13,\dots.
\end{align*}
The first two are described by $x_{n_k} = x_{2k}$ and $x_{n_k} = x_{2k-1}$ respectively. 

\begin{question}
How would we describe the third?
\end{question}

Continuing to let $\{x_n = n\}_n$, the following are \textit{not} subsequences:
\begin{align*}
    &1,1,1,1,1,1,\dots \\
    &1,1,3,3,5,5,\dots.
\end{align*}

Now consider the sequence $\{(-1)^n\}$. Then we have the subsequences
\begin{align*}
    x_{n_k} = x_{2k-1} &\to  -1,-1,-1,\dots \\
    y_{n_k} = x_{2k} &\to  1,1,1,\dots.
\end{align*}

\begin{theorem}
If $\{x_n\}$ converges to $x$, then any subsequence of $x_n$ will converge to $x$.
\end{theorem}
\textbf{Proof}: Suppose $\lim_{n\to \infty}x_n = x$. Let $\epsilon >0$. Then, $\exists M_0 \in \NN$ such that $\forall n\geq M_0$,
\[
|x_n-x|<\epsilon.
\]
Choose $M = M_0$. If $k\geq M$, then $n_k \geq k \geq M = M_0$. Hence, for all $\epsilon>0$ there exists an $M$ such that for all $n_k >M$,
\[
|x_{n-k}-x|<\epsilon.
\]
\qed 

\begin{remark}
Notice that this also implies that the sequence $\{(-1)^n\}_n$ is divergent.
\end{remark}

\begin{notation}[DNC]
We can denote the statement "a sequence does not converge"/"a sequence is divergent" as "the sequence DNC".
\end{notation}