序列(Sequence)

單調序列 (Monotonic sequences)

• 令 $\lbrace s_n \rbrace$ 為實數序列。
• 單調遞增序列(increasing sequence): $s_n \leq s_{n+1}$, $\forall n \in \mathbb{N}$.
• 單調遞減序列(decreasing seqeunce): $s_n \geq s_{n+1}$, $\forall n \in \mathbb{N}$.

收斂序列 (Convergence sequences)

• A sequence $\lbrace p_n \rbrace$ in metric space $(X, d)$ is said to be converge in $X$ if there is a point $p \in X$ such that:

  • $\forall \epsilon > 0$ $\exists \ n_0 \in \mathbb{N}$ $\ni \ d(p_n, p) < \epsilon$, $\forall n \geq n_0$.

  • 通常寫為 $\lim_{n \rightarrow \infty} p_n = p$ or $p_n \rightarrow p$.

  • 收斂可解釋為只要$n$夠大，sequence與收斂值之間的差距可以任意小。

• If $\lbrace p_n \rbrace$ does not converge, it is said to diverge (發散) .

• Sequence是否收斂，除了自身的特性外，還必須確認收斂點$p$是否為metric space中的元素。

  • E.g. $\lbrace 1/n \rbrace$在$\mathbb{R}$會收斂到0，但在$\mathbb{R}^+$, with metric $\rho(x,y)=\vert x-y \vert$不收斂，因$0 \notin \mathbb{R}^+$.

• Theorem: Let $\lbrace p_n \rbrace$ be a sequence in a metric space $X$., then

  • $\lim_{n \rightarrow \infty} p_n = p \in X \Leftrightarrow$ every neighborhood of $p$ contains all but finitely many of the terms of $\lbrace p_n \rbrace$.

  • (收斂的唯一性) Let $p_1, p_2 \in X$, $\lim_{n \rightarrow \infty} p_n = p_1$ and $\lim_{n \rightarrow \infty} p_n = p_2$ then $p_1 = p_2$.

  • (收斂序列必有界) If $\lbrace p_n \rbrace$ converges, then $\lbrace p_n \rbrace$ bounded.

  • If $E \subset X$ and $p$ is a limit point of $E$ then there is a sequence $\lbrace p_n \rbrace$ in $E$ such that $\lim_{n \rightarrow \infty} p_n = p$.

Sequence 運算

• Let $\lbrace s_n \rbrace$ and $\lbrace t_n \rbrace$ are complex sequences, $\lim_{n \rightarrow \infty} s_n = s$ and $\lim_{n \rightarrow \infty} t_n = t$ then

  • $\lim_{n \rightarrow \infty} (s_n + t_n ) = s+t$.

  • $\forall c \in \mathbb{C}$, $\lim_{n \rightarrow \infty} cs_n = cs$, $\lim_{n \rightarrow \infty} (c + s_n) = c + s$.

  • $\lim_{n \rightarrow \infty} s_n t_n = st$.

  • $\lim_{n \rightarrow \infty} \frac{1}{n} = \frac{1}{s}$ if $s_n \neq 0 \ \forall n$ and $s \neq 0$.

Subsequence

• Subsequence為sequence中不連續的元素(但順序不變)所形成的序列，與演算法中subsequence定義相同。

• Definition

  • Given a sequence $\lbrace p_n \rbrace$, consider a sequence $\lbrace n_k \rbrace$ of positive integers such that $n_1 < n_2 < \cdots < n_k < \cdots$ then the sequence $\lbrace p_{n_k} \rbrace$ is called subsequence of $\lbrace p_n \rbrace$.

• If $\lim_{n \rightarrow \infty} p_n = p$ $\Leftrightarrow$ every subsequence of $\lbrace p_n \rbrace$ converges to $p$.

• Theorem: If $\lbrace p_n \rbrace$ is a sequence in a compact metric space $(X, d)$, then some subsequence of $\lbrace p_n \rbrace$ converges to a point of $X$.

Cauchy sequence

• Definition

  • A sequence $\lbrace p_n \rbrace$ in m a metric space $(X, d)$ is said to be a Cauchy sequence if $\forall \epsilon > 0$ $\exists n_0 \in \mathbb{N}$ $\ni d(d(p_n, p_m) < \epsilon$, $\forall n, m > n_0$.

  • Cauchy sequence可用於判定sequence的收斂性，而不需要知道sequence收斂之值為何。

• E.g. $\mathbb{R}^n \ \forall n$ are complete metric spaces, 所有的Cauchy sequences均收斂。

  • Converge sequence $\Rightarrow$ Cauchy sequence。反之不一定成立，必須要加上compact metric space $X$的條件以保證收斂值位於metric space中。

• Properties:

  • $E \subset X$ is called bounded set if $diamE < \infty$.

  • If $\lbrace p_n \rbrace$ is a sequence in $X$ and $E_N$ consists of the points $p_N, p_{N+1}, p_{N+2}, \cdots$, then $\lbrace p_n \rbrace$ is a Cauchy sequence $\Leftrightarrow$ $\lim_{N \rightarrow \infty} diamE_N = 0$.

  • If $\bar{E}$ is the closure of a set $E \subset X$, then $diam\bar{E} = diamE$.

  • If $k_n$ is a sequence of compact sets in $X$, $k_n \supset k_{n+1}$ $\forall n \in \mathbb{N}$, and if $\lim_{n \rightarrow \infty} diam k_n =0$, then $\cap_{n=1}^{\infty}k_n$ conststs of exactly one point.

發散序列(Divergence sequence)

• 定義: 發散序列( Divergence sequence)
  • 令 $\lbrace s_n \rbrace$ 為實數序列且有以下性質:
  • (往正無窮大發散) $\forall M \in \mathbb{R}$ $\exists n_0 \in \mathbb{N}$ $\ni s_n \geq M$ $\forall n \geq n_0$. usually denoted as $\lim_{n \rightarrow \infty} s_n \rightarrow +\infty$.
  • (往負無窮大發散) $\forall M \in \mathbb{R}$ $\exists n_0 \in \mathbb{N}$ $\ni s_n \leq M$ $\forall n \geq n_0$, usually denoted as $\lim_{n \rightarrow \infty} s_n \rightarrow -\infty$.

序列的上極限

• 定義: 序列的上極限(upper limit of sequence)
  • 令序列 $\lbrace s_n \rbrace$ 有上界且 $M_n = \sup \lbrace s_n, s_{n+1}, s_{n+2}, \cdots,\rbrace,$ 則 $M_n \geq M_{n+1} \geq M_{n+2}, \cdots$.
  • 若序列 $M_n$ 收斂, 則序列 $\lbrace s_n \rbrace$ 的上極限寫為 $\lim \sup_{n \rightarrow \infty} s_n = \lim_{n \rightarrow \infty} M_n$
  .
  • 若序列 $M_n$ 發散, 則序列的上極限也發散， $\lim \sup_{n \rightarrow \infty} s_n = \infty$.
  • 若序列 $\lbrace s_n \rbrace$ 無上界，則序列的上極限發散， $\lim \sup_{n \rightarrow \infty} s_n = \infty$.
  • $\lim \sup_{n \rightarrow \infty} s_n = \lim_{n \rightarrow \infty} \left( \sup_{m \geq n} s_m \right) = \inf_{n \geq 0} \sup_{ k \geq n} s_k = \inf \{ \sup\{ s_k| k \geq n \} | n \geq 0 \}$
  • $\lim \sup_{n \rightarrow \infty} s_n = - \lim \inf_{n \rightarrow \infty} - s_n$.

• 令$M$為序列$\{s_n\}$的上極限，則必須滿足以下兩個條件：

  • $\forall \epsilon > 0\ \exists n_0 \in \mathbb{N} \ni s_n < M + \epsilon \ \forall n \geq n_0$.
    • 此條件為序列極限有上界，但不唯一。
    • $a,b \in \mathbb{R},\ a < b \Leftrightarrow \forall \epsilon > 0,\ a < b+ \epsilon$.
  • $\exists \epsilon > 0 \text{ and } n_1 \in \mathbb{N} \ni s_n > M - \epsilon \ \forall n \geq n_1$.
    • 此條件為序列中有無窮多個元素(但非全部)落於$M-\epsilon$的右側。
  • 滿足以上兩個條件時，寫為$\lim \sup_{n \rightarrow \infty} s_ = M$.

• E.g. $\lbrace s_n \rbrace = \lbrace (-1)^n \rbrace$，$\forall n \in \mathbb{N}$，可知$\lbrace s_n \rbrace$在$-1$與$1$間振盪，所以$\lim \sup s_n = 1$, and $\lim \inf s_n = -1$.

• E.g. $\lbrace s_n \rbrace = \lbrace -n \rbrace$ is bounded above, and $\forall n \in \mathbb{N}$, $M_n = -n$, $\therefore \lim \sup_{n \rightarrow \infty} s_n = -\infty$.

數列的下極限

• 定義: 序列的下極限(lower limit of sequence)

• E.g. $\lim \inf_{n \rightarrow \infty }(-1)^n = -1$.

• E.g. $\lim \inf_{n \rightarrow \infty} n = \infty$.

• E.g. $\lim \inf_{n \rightarrow \infty} (-n) = -\infty$.