Skip to main content

Mathematical Analysis

Sam Macdonald

Section 2.2 Subsequences

“Elegance comes from being as beautiful inside as outside.”
―Coco Chanel

Definition 2.18. Subsequence.

Let \((x_n)_{n=1}^{\infty}\) be a sequence (in any set \(S\)). A subsequence of \((x_n)_{n=1}^{\infty}\) is a sequence \((x_{f(n)})_{n=1}^{\infty}\) where \(f:\mathbb{Z}_{\geq 1}\rightarrow\mathbb{Z}_{\geq 1}\) is a strictly increasing function

Example 2.19.

\((x_{2n})_{n=1}^{\infty}\) and \((x_{2n+1})_{n=1}^{\infty}\) are subsequences of \((x_n)_{n=1}^{\infty}\text{.}\)

Convention 2.20.

We'll usually write \((x_{n_k})_{k=1}^{\infty}\) for a subsequence of \((x_n)_{n=1}^{\infty}\text{.}\) (Here \(({n_k})_{k=1}^{\infty}\) is a strictly increasing set of positive integers)
A subsequence of a subsequence of \((x_n)_{n=1}^{\infty}\) is a subseqeuence of \((x_n)_{n=1}^{\infty}\text{.}\)
Suppose b1, b2,... is a strictly increasing sequence of natural numbers. We prove bn ≥ n for all n by induction on n. That is, for each n ∈ N, let Pn be the statement that bn ≥ n.
P1 is true since b1 ∈ N and so b1 ≥ 1. Given k ∈ N, assume Pk is true; that is, assume bk ≥ k. Since bk+1 > bk and both are natural numbers, we have bk+1 ≥ bk + 1 ≥ k + 1; that is, Pk+1 is true too. By induction, Pn is true for all n ∈ N.
Let the sequence \{a_n\}^\infty_{n=1} converge to L, and take a subsequence {ank }∞ k=1 for some strictly increasing sequence n1 < n2 < n3 < · · · of natural numbers.
Let ε > 0. Since \{a_n\}^\infty_{n=1} converges to L, there is some N ∈ R such that for all natural numbers n > N we have |an − L| < ε. We claim that the same N works to verify the definition of {ank }∞ k=1 converges to L for this ε. Indeed, if k > N, then nk > N, so |ank − L| < ε. Thus, {ank }∞ k=1 converges to L.
  1. Assume that the set of values {an | n ∈ N} does not have a maximum value.
    We define a subsequence recursively. We will recursively choose natural numbers n1, n2, n3,... so that nk < nk+1 for all k and ank ≤ ank+1.
    We start by setting n1 = 1.
    If we have chosen nk, then let b = max{a1,..., ank }.
    We claim that there is some m > nk such that am > b. To obtain a contradiction, suppose otherwise. Then for any n ∈ N, either n > nk and an ≤ b by assumption, or n ≤ nk and an ≤ b, since an is on the list of things of which b was the maximum. Then b is the maximum of {an | n ∈ N}, which yields a contradiction. Thus, there is some m > nk such that am > b, and we can choose m = nk+1. Thus, we can define such a sequence recursively.
  2. Similar to (1), or apply (1) to {−an}∞n=1.
Let \{a_n\}^\infty_{n=1} be any sequence. Recall that our goal is to prove it either has an increasing subsequence or it has a decreasing subsequence. This is equivalent to showing that if it has no increasing subsequences, then it does have at least one decreasing subsequence. So, let us assume it has no increasing subsequences.
We will prove it has at least one decreasing subsequence by constructing the indices n1 < n2 < · · · of such a subsequence recursively. By the contrapositive of part (1) Lemma 16.4, since \{a_n\}^\infty_{n=1} does not contain any increasing subsequences, we know that {an | n ∈ N} has a maximum value. That is, there exists a natural number n1 such that an1 ≥ am for all m ≥ 1.
For any k, given nk, the subsequence ank +1, ank +2, ank +3,... also has no increasing subsequence, since a subsequence of such a sequence is a subsequence of the original sequence too. Thus, it must have a maximum value again by part (1) Lemma 16.4; choose nk+1 such that ank+1 = max{ank +1, ank +2, ank +3,... }. By construction, we have nk+1 > nk. Thus, this gives a recursive definition for nk.
For any k, note that ank is the maximum of a set that contains ank+1 (since it is later in the sequence). It follows that ank ≥ ank+1. That is, we have constructed a decreasing subsequence of the original sequence.
Suppose \{a_n\}^\infty_{n=1} is a bounded sequence. By the Bolzano-Weierstrass Theorem 16.3 it admits a monotone subsequence {ank }∞ k=1, and it too is bounded (since any subsequence of a bounded sequence is also bounded.) The result follows since every monotone bounded sequence converges by the Monotone Convergence Theorem 11.4.
<Prev^TopNext>