$\newcommand{\Rr}{\mathbb{R}}$ $\newcommand{\Zz}{\mathbb{Z}}$ $\newcommand{\Nn}{\mathbb{N}}$ $\newcommand{\Qq}{\mathbb{Q}}$ $\newcommand{\ve}{\varepsilon}$ $\newcommand{\seq}[1]{\left( #1 \right)}$ $\newcommand{\va}{\mathbf{a}}$ $\newcommand{\vb}{\mathbf{b}}$ $\newcommand{\vc}{\mathbf{c}}$ $\newcommand{\vx}{\mathbf{x}}$ $\newcommand{\vy}{\mathbf{y}}$ $\newcommand{\vz}{\mathbf{z}}$ $\newcommand{\norm}[1]{\left\| #1 \right\|}$

Sequences¶

Read Section 2.1, 2.2. Also, review the materials about sequences from Calculus II.

Notation.

  • For sequences, we use the notation $\seq{x_n}$ (the textbook notation is $\{x_n \}$).

  • We also write $x_n \to L$ for $\lim_{n \to \infty} x_n = L$.

  • For $n \gg 0$ means "for all sufficiently large $n$". That is the phrase "there exists $N$ such that for all $n \ge N$."

  • The usual logic convention for free variables in a sentence means the quantifier is the universal, i.e. for all. For example. "suppose $x_n \ge 0$." means "suppose $x_n \ge 0$ for all $n$.

Definitions¶

An infinite sequence is a function with domain $\Nn$.

Since we mainly focus on infinite sequences, we simply refer them as sequences.

If $x$ is the name of a sequence, we write $x_n$ for its value at $n$ and call it the $n$-th term of the sequence. We use $\seq{x_n}$ to denote the sequence.

As a real-valued function, we understand what means by a sequence of real numbers is bounded above, (bounded below, increasing, decreasing,...)

Example

  • $\seq{1/n}$ is decreasing and bounded.

  • $\seq{n}$ is increasing and bounded below but not bounded above.

  • $\seq{(-1)^n}$ is bounded but neither increasing nor decreasing.

The following observation are clear:

  1. an increasing (resp. a decreasing) sequence is always bounded below (resp. bounded above).

  2. Constant sequences are precisely those that are both increasing and decreasing.

A sequence of real numbers $\seq{x_n}$ is null (or converging to 0) if for any $\ve > 0$, there exists $N \in \Nn$ such that $$|x_n| < \ve \quad \text{for all}\ n \ge N $$

In other words, $\seq{x_n}$ is null if for any $\ve > 0$, $|x_n| < \ve$ for all but finitely many $n$.

Yet in other words, $\seq{x_n}$ is null if for any $\ve >0$, the set $$\{n \in \Nn \colon |x_n| < \ve\}$$ is cofinite in $\Nn$ (i.e. its completement is a finite subset of $\Nn$).

Example The sequence $\seq{1/n}$ is null.

We say that a sequence $\seq{x_n}$ converges to a real number $L$, written as $x_n \to L$ (or $\lim x_n = L$), if the sequence $\seq{x_n -L}$ is null.

If $\seq{x_n} \to L$, then we say that $L$ is a limit of the sequence $\seq{x_n}$.

A sequence is convergent if it has a limit. A divergent sequence is a sequence that is not convergent.

Fundamental results of convergence of real sequences¶

Since $|x_n| = |-x_n| = ||x_n||$, so we immediately have

Lemma 1. $\seq{x_n}$ is null $\iff$ $\seq{-x_n}$ is null $\iff$ $\seq{|x_n|}$ is null.

Lemma 2. If $\seq{x_n}$ is null and $\seq{y_n}$ is bounded then $\seq{x_ny_n}$ is null.

Proof Since $\seq{y_n}$ is bounded, there exists some $B$ such that $|y_n| \le B$ for each $n$. Since $\seq{x_n}$ is null, for any $\ve >0$, since $\ve/B$ is also positive, $|x_n| < \ve/B$ for all but finitely many $n$ and hence

$$|x_n y_n| < B(\ve/B) = \ve $$

for all but finitely many $n$. This completes the proof.

Since constant sequences are bounded, so for any $c \in \Rr$, $\seq{cx_n}$ is null whenever $\seq{x_n}$ is null.

Lemma 3. If $\seq{x_n},\seq{y_n}$ are null then so is $\seq{x_n+y_n}$.

Proof. For any $\ve > 0$, there exist $N_1,N_2$ such that $|x_n| < \ve/2$ for all $n \ge N_1$ and $|y_n| < \ve/2$ for all $n \ge N_2$. Since $|x_n+y_n| \le |x_n| + |y_n|$ by the triangle inequality and so,

$$|x_n+y_n| \le |x_n| + |y_n| < \ve/2 + \ve/2 = \ve$$

whenever $n \ge \max\{N_1, N_2\}$.

Proposition 1. A convergent sequence has a unique limit.

Proof. Suppose $L$ and $L'$ are limits of a convergent sequence $\seq{x_n}$. Then both $\seq{L-x_n}$ and $\seq{x_n-L'}$ are null and so is the sum (Lemma 3.) which is the constant sequence $\seq{L-L'}$. But a constant sequence is null sequence means its terms are all zero. Therefore, $L - L' = 0$, i.e. $L = L'$.

Proposition 2. A convergent sequence is bounded.

Proof. Suppose $x_n \to L$, then there exists $N \in \Nn$ such that $|x_n-L| < 1$ whenever $n \ge N$. Thus, by the triangle inequality, whenever $n \ge N$,

$$|x_n|-|L| \le ||x_n|-|L|| \le |x_n-L| < 1.$$

Consequently, $|x_k| \le B:=\max\{|x_1|, \ldots, |x_{N-1}|, 1+|L|\}$ for all $k \in \Nn$.

Theorem 3 (monotone convergence theorem)

A bounded increasing (resp. decreasing) sequence $\seq{x_n}$ converges to $\sup\{x_n\colon n \in \Nn\}$ (resp. $\inf \{x_n \colon n \in \Nn\}$.)

Proof. We will only prove the case for increasing sequence. The set of terms $S = \{x_n \colon n \in \Nn\}$ is bounded above by the assumption and is non-empty since $x_1 \in S$. Therefore, $s :=\sup S$ exists by the least upper bound property. For any $\ve >0$, $s-\ve$ cannot be an upper bound of $S$. Thus, $s -\ve < x_N$ for some $N \in \Nn$. Since $\seq{x_n}$ is increasing, for all $n \ge N$, $$s-\ve < x_N \le x_n \le s$$

This shows that $x_n \to s$.

The next proposition states that various operations on convergent sequences result in a convergent sequence and taking limit commutes with these operations.

Attention should be paid on the assumptions of these results. Find examples that show these assumptions are necessarily.

Proposition 6. Suppose $a_n \to A$ and $b_n \to B$, then

  1. $a_n + b_n \to A+B$
  2. $a_nb_n \to AB$.
  3. $(1/a_n) \to 1/A$ provided that $A \neq 0$.

Proof. (1) $\seq{a_n-A}$ and $\seq{b_n-B}$ are both null. By Lemma 2, their sum $\seq{a_n-A} + \seq{b_n-B} = \seq{(a_n+b_n)-(A+B)}$ is a null sequence as well. That means $(a_n+b_n) \to A+B$.

To prove (2), note that

$$a_nb_n - AB = (a_nb_n - a_nB) + (a_nB-AB) = a_n(b_n-B)+(a_n-A)B.$$

The sequence $\seq{a_n}$ is bounded since it is convergent (Proposition 2). Therefore, $\seq{a_n(b_n-B)}$ is null (Lemma 3). Moreover, since $\seq{a_n-A}$ is null so is $\seq{(a_n-A)B}$. Thus, as the sum of two null sequences, $\seq{a_nb_n-AB}$ is null, i.e. $a_nb_n \to AB$, as well.

For the 3rd statement, since $A \neq 0$, so $|a_n| > |A|/2 > 0$ for all $n \gg 0$. (So $a_n$ can be zero and hence $(1/a_n)$ is not defined by at most finitely many terms). Thus,

$$\left| \frac{1}{a_n} - \frac{1}{A}\right| = \frac{|a_n -A|}{|a_n||A|} < \frac{2}{|A|}|a_n-A|.$$

Since $|a_n-A| \to 0$, the inequality above shows that $1/a_n \to A$.

Squeeze Lemma. Suppose $a_n \le x_n \le b_n$ for all $n \in \Nn$ and $\seq{a_n}$, $\seq{b_n}$ have the same limit $L$. Then $\seq{x_n}$ converges to $L$.

Proof. Since both $\seq{a_n-L}$ and $\seq{b_n-L}$ are null, for any $\ve > 0$, $$ -\ve < a_n - L, b_n-L < \ve $$ for all sufficiently large $n$. And since $a_n -L \le x_n -L \le b_n-L$ for all $n$, so $-\ve < x_n -L < \ve$ for all sufficiently large $n$. That means $x_n \to L$.

Proposition 7. Let $S \subset \Rr$ be a nonempty set that is bounded above (resp bounded below). Then there exists an increasing sequence $\seq{x_n}$ (resp. a decreasing sequence $\seq{y_n}$) of elements of $S$ such that

$$ \sup S = \lim x_n \quad (\text{resp. } \inf S = \lim y_n). $$

Proof. We prove that for the case when $S$ is bounded below. Let $a$ be the infimum of $S$. If $a \in S$, then simply take $y_n=a$ for each $n$. Thus, we can assume $a \notin S$ and we have $a \lt y$ for any $y \in S$.

We are going to construct a sequence $\seq{y_n}$ with the required property inductively. Take $y_1 \in S$ arbitrarily. Suppose for $k \ge 1$, we find $y_1, \ldots y_k \in S$ such that $$ a < y_k < \cdots < y_1 $$

and $y_k -a \le \dfrac{y_1-a}{2^{k-1}}$. Since $a < m:=\dfrac{y_k+a}{2} < y_k$, $m$ is not a lower bound of $S$ and hence there exists $y_{k+1} \in S$ such that $a < y_{k+1} < m$. Consequently,

$$0 < y_{k+1}-a < m-a = \frac{y_k+a}{2} - a = \frac{y_k-a}{2} \le \frac{y_1-a}{2^k}.$$

Thus, by induction we constructed a decreasing sequence $\seq{y_n}$ in $S$ such that for all $n \ge 1$, $$ 0< y_n -a \le \frac{y_1-a}{2^{n-1}} $$ Since $(y_1-a)/2^{n-1} \to 0$ so $y_n \to a$ by the squeeze lemma.

Proposition 8. If $\seq{x_n}$ is convergent and $x_n \ge 0$, then $\lim x_n \ge 0$.

Proof. Suppose $\seq{x_n} \to L$ but $L < 0$. Since $x_n \ge 0$ and $L <0$, so for any $n$,

$$ |x_n - L| = x_n - L \ge 0-L = |L| >0.$$

This contradicts $\lim x_n = L$.

Note that we cannot conclude that the limit of a sequence of positive numbers is positive, e.g. $(1/n)$.

Corollary 9. If $\seq{x_n},\seq{y_n}$ are convergent and $y_n \ge x_n$ for all $n$, then $\lim y_n \ge \lim x_n$.

Proof. Let $z_n = y_n-x_n$. Then the sequence $(z_n)$ is convergent and $z_n \ge 0$ for all $n$. So by Proposition 8. $\lim z_n \ge 0$. But $\lim z_n = \lim y_n - \lim x_n$. And so we have $\lim y_n \ge \lim x_n$.

Subsequence¶

A subsequence of a sequence $(a_n)$ is a sequence of the form $(a_{n_k})_k$ where $(n_k)$ is a strictly increasing sequence of natural numbers.

Proposition 10. Two sequences differ by finitely many terms have the same convergence--that is either both converge to the same limit or both are divergent. Consequently if a sequence is obtained from another by dropping finitely many terms, then they have the same convergence.

Proposition 11. Every subsequence of a convergent sequence has the same limit as the sequence.

Proof. Suppose $x_n \to L$ and $(x_{n_k})$ is a subsequence of $\seq{x_n}$. For any $\varepsilon > 0$, there exists $N \in \Nn$, such that

$$ |x_n -L| < \varepsilon, \forall n \ge N \tag{*}$$

Since $(n_k)$ is a strictly increasing sequence of natural numbers, $n_k \ge k$ for all $k$.

Therefore, if $k \ge N$, then so is $n_k$ and hence $|x_{n_k} - L| < \varepsilon$ according to $(*)$. This show that $x_{n_k} \to L$ as $k \to \infty$.