> [!definition] > > Let $A$ be a [[Set|set]], the [[Function|function]] $x: I \mapsto A$ is an $A$-valued sequence indexed by the set $I$. The $i$-th value of the sequence $x$ is denoted as $x_{i}$. An entire sequence may be denoted as a list of all its elements $(x_1, x_2, \cdots)$. > [!definition] > > A sequence $(x_n)$ is *increasing* if $x_{i} \ge x_{j} \forall i, j \in I, i \ge j$. A sequence is *decreasing* if $x_i \le x_j \forall i, j \in I, i \ge j$. A sequence is **monotone** if it is increasing or decreasing. > [!definition] > > Let $(x_n)$ be a sequence. The sequence $x_{n_1}, x_{n_2}, \cdots, x_{n_{j}}, \cdots$, where $n_1, n_2, \cdots, n_j \cdots$ is a strictly increasing sequence of natural numbers[^1], is a *subsequence* of $(x_n)$. > [!theorem] > > Every sequence contains a monotone subsequence. > > *Proof*. Let $(x_n)$ be a sequence of real numbers. An element $x_m$ is a *peak* of the sequence if $x_{m} \ge x_{n}$ for all $n \ge m$. If a sequence is increasing, then it has no peaks, but then the entire sequence would be monotone. If a sequence has finitely many peaks, then it is *eventually* increasing, and the sequence after the last peak would be monotone. If a sequence has infinitely many peaks, then the sequence of peaks will be a decreasing sequence. > [!definition] > > Let $(x_n)$ be a sequence. $(x_n)$ is called *contractive* if $\exists c \in (0, 1)$ such that > $ > |x_{n + 2} - x_{n + 1}| < c|x_{n + 1} - x_n| \quad \forall n \in \nat > $ > [!theorem] > > All *contractive* sequences are [[Cauchy Sequence|Cauchy]], and therefore convergent. > > *Proof*. Note that the differences between terms behave as a sequence of exponents ($c, c^2, c^3 \cdots$), and their sum form the [[Geometric Series|geometric series]], which is convergent. The further into the sequence, the smaller these differences become, exponentially. Therefore, the series is Cauchy, and convergent. [^1]: Or some discrete, partially ordered set. *Or*, an *unbounded* increasing sequence of any index set.