Subsequences

Selecting Terms Without Changing Their Order

A sequence can be studied through selected terms rather than through every term. The selection must preserve the original order: a later selected term must come from a later index. For example, selecting terms at indices \(0,2,4,\ldots\) gives one sequence, while selecting terms at indices \(1,3,5,\ldots\) gives another. These selections can reveal different behavior already present in the original sequence.

The key requirement is an infinite, strictly increasing list of indices. Repeating an index would repeat the same position in the original sequence, and choosing indices out of order would rearrange its terms. Neither operation is part of forming a subsequence.

The index sequence \((n_k)\) is sometimes called the subsequence’s index map. For instance, \(n_k=2k\) selects the even-indexed terms, while \(n_k=2k+1\) selects the odd-indexed terms. Both choices are strictly increasing for \(k\in\mathbb{N}_0\), so each defines a subsequence.

A subsequence may omit finitely many terms, infinitely many terms, or no terms at all. It cannot stop after a finite selection: a subsequence is itself an infinite sequence. The original sequence is also a subsequence of itself, by taking \(n_k=k\).

Selected Indices Always Move Forward

Strict increase of the indices has an important consequence: a subsequence cannot remain confined to a finite part of the original sequence. In fact, its \(k\)-th index is at least \(k\).

Proof. We use induction on \(k\). Since \(n_0\) is a nonnegative integer, \(n_0\geq0\). Now suppose \(n_k\geq k\). The strict inequality \(n_{k+1}>n_k\), together with the fact that both are integers, implies \(n_{k+1}\geq n_k+1\). Therefore

This proves \(n_k\geq k\) for every \(k\). Given any fixed \(N\in\mathbb{N}_0\), if \(k\geq N\), then \(n_k\geq k\geq N\). Thus all selected indices from position \(N\) onward are at least \(N\), as claimed. \(\square\)

The bound \(n_k\geq k\) does not say that every subsequence selects the \(k\)-th term at index \(k\), or even that it stays close to that index. It says only that the \(k\)-th selected index cannot be earlier than \(k\). For example, the choices \(n_k=3k+2\) and \(n_k=(k+1)^2\) both move forward, but at different rates.

Properties Inherited by Subsequences

A subsequence uses terms already present in the original sequence. Consequently, any bound that applies to every original term also applies to every selected term. Order properties pass to subsequences for a related reason: strictly increasing indices ensure that the original terms are selected in the same order in which they occur.

Proof. Let \((a_{n_k})\) be a subsequence of \((a_n)\). If \(L\leq a_n\leq U\) for every \(n\in\mathbb{N}_0\), then in particular this inequality holds at every selected index \(n_k\). Thus

for every \(k\), so the same bounds apply to the subsequence.

Now suppose \((a_n)\) is nondecreasing. If \(j<k\), the strict increase of the indices gives \(n_j<n_k\). By the pairwise comparison property for nondecreasing sequences established earlier in this course, \(a_{n_j}\leq a_{n_k}\). Hence the subsequence is nondecreasing. If \((a_n)\) is nonincreasing, the same comparison property gives \(a_{n_j}\geq a_{n_k}\), so the subsequence is nonincreasing.

If the original sequence is strictly increasing, \(n_j<n_k\) implies \(a_{n_j}<a_{n_k}\), using the corresponding pairwise comparison property for strictly increasing sequences. The subsequence is therefore strictly increasing. If the original sequence is strictly decreasing, the same reasoning gives \(a_{n_j}>a_{n_k}\), so the subsequence is strictly decreasing. \(\square\)

The boundedness part of the theorem is a direct inheritance of the original bounds. The monotonicity part depends on preserving index order; it would not be true for an arbitrary rearrangement of the terms. For example, reversing selected terms could turn an increasing finite list into a decreasing one, but that reversal is not a subsequence selection.

Subsequences of Eventually Monotone Sequences

The same inheritance principle applies when monotonicity holds only after a finite initial segment. The selected terms might include several irregular early terms, but sufficiently late positions in the subsequence come from the monotone tail of the original sequence.

Proof. Let \((a_{n_k})\) be a subsequence, and suppose first that \((a_n)\) is eventually nondecreasing. Choose \(N\in\mathbb{N}_0\) such that \(a_m\leq a_n\) whenever \(N\leq m\leq n\), using the pairwise comparison theorem for eventually nondecreasing sequences. By the lemma, \(n_k\geq k\). Thus if \(k\geq N\), then \(n_k\geq N\). For any \(j,k\) with \(N\leq j\leq k\), we have \(N\leq n_j\leq n_k\). Therefore

The subsequence is nondecreasing from position \(N\) onward, so it is eventually nondecreasing.

If instead \((a_n)\) is eventually nonincreasing, choose \(N\) so that \(a_m\geq a_n\) whenever \(N\leq m\leq n\). For \(N\leq j\leq k\), the index inequalities \(N\leq n_j\leq n_k\) then give \(a_{n_j}\geq a_{n_k}\). Thus the subsequence is eventually nonincreasing. An eventually monotone sequence satisfies one of these two alternatives, which proves the final claim. \(\square\)

The lemma is what connects the threshold in the original sequence to a threshold for the subsequence. Merely knowing that the original sequence has a monotone tail is not enough to say that every selected term lies in that tail; some early selected terms may come before it. The index bound ensures that only finitely many positions of the subsequence can do so.

Taking a Subsequence More Than Once

A selection can be applied to a sequence that is already a subsequence. The result is still a subsequence of the original, because composing two order-preserving index choices produces another strictly increasing index choice.

Proof. Write the first subsequence as \((a_{n_k})_{k=0}^{\infty}\), where \(n_0<n_1<\cdots\). Let a subsequence of it be formed using strictly increasing nonnegative integer indices \(m_0<m_1<\cdots\). Its terms are

If \(i<j\), then \(m_i<m_j\). Since \((n_k)\) is strictly increasing, it follows that \(n_{m_i}<n_{m_j}\). Hence the composed indices \(n_{m_0},n_{m_1},\ldots\) are strictly increasing nonnegative integers. They therefore define a subsequence of the original sequence, and its terms are exactly those obtained by the second selection. \(\square\)

This result is useful when selections are made in stages. One may first retain a convenient group of terms and then select from that group, without changing what counts as a subsequence of the starting sequence. The final order still agrees with the original order.

What the Definition Rules Out

A subsequence is not simply any sequence whose values also occur somewhere in the original. Its terms must arise from a strictly increasing sequence of indices. This distinction rules out both repetition of a single index and reordering.

• Choosing indices \(0,2,5,\ldots\) is permitted if the entire list continues strictly increasingly.
• Choosing an index twice is not permitted, even if the repeated values happen to be equal.
• Choosing indices in the order \(4,1,7,\ldots\) is not permitted, because the indices do not increase.
• A subsequence need not include every term, and it need not include a fixed proportion of the original terms.

Equal values in the original sequence cause no difficulty. A subsequence may contain equal consecutive values if they occur at distinct indices. What is forbidden is repeating an index, not selecting two different positions whose terms have the same value.

The main inheritance results are useful precisely because they require no extra assumptions about which indices are selected beyond strict increase. Bounds and monotonicity already present in the original sequence remain valid along the selected terms, while eventual monotonicity remains valid after at most finitely many selected positions. A subsequence may reveal a pattern more clearly, but it cannot create a term that the original sequence did not have or reverse the order in which terms appeared.