# Subsequence

## Definition

Given a sequence [ilmath](x_n)_{n=1}^\infty[/ilmath] we define a subsequence of [ilmath](x_n)^\infty_{n=1}[/ilmath][1][2] as follows:

• Given any strictly increasing monotonic sequence[Note 1], [ilmath](k_n)_{n=1}^\infty\subseteq\mathbb{N}[/ilmath]
• That means that [ilmath]\forall n\in\mathbb{N}[k_n<k_{n+1}][/ilmath][Note 2]

Then the subsequence of [ilmath](x_n)[/ilmath] given by [ilmath](k_n)[/ilmath] is:

• [ilmath](x_{k_n})_{n=1}^\infty[/ilmath], the sequence whose terms are: [ilmath]x_{k_1},x_{k_2},\ldots,x_{k_n},\ldots[/ilmath]
• That is to say the [ilmath]i[/ilmath]th element of [ilmath](x_{k_n})[/ilmath] is the [ilmath]k_i[/ilmath]th element of [ilmath](x_n)[/ilmath]

### As a mapping

Consider an (injective) mapping: [ilmath]k:\mathbb{N}\rightarrow\mathbb{N} [/ilmath] with the property that:

• [ilmath]\forall a,b\in\mathbb{N}[a<b\implies k(a)<k(b)][/ilmath]

This defines a sequence, [ilmath](k_n)_{n=1}^\infty[/ilmath] given by [ilmath]k_n:= k(n)[/ilmath]

• Now [ilmath](x_{k_n})_{n=1}^\infty[/ilmath] is a subsequence

## Immediate properties

[ilmath]\forall n\in\mathbb{N}[k_n\ge n][/ilmath] - the [ilmath]k_i[/ilmath]th term of a subsequence cannot correspond to any element before the (but not including) [ilmath]i[/ilmath]th term of the main sequence

This is a standard proof by induction.

1. Suppose [ilmath]n\eq 1[/ilmath], show [ilmath]k_1\ge 1[/ilmath]
• Well [ilmath]k_1[/ilmath] is the first term of the subsequence and this may be the 1st term of the sequence, in which case we have [ilmath]k_1\eq 1[/ilmath] thus [ilmath]k_1\ge 1[/ilmath] holds
• If the first term of the subsequence is any term other than the first we see [ilmath]k_1>1[/ilmath] and so [ilmath]k_1\ge 1[/ilmath] holds
2. Assuming we have [ilmath]k_n\ge n[/ilmath] show that this implies [ilmath]k_{n+1}\ge n+1[/ilmath]
• We have [ilmath]k_n\ge n[/ilmath] by assumption, and we wish to show [ilmath]k_n\ge n\implies k_{n+1}\ge n+1[/ilmath]
• By definition of subsequence we see [ilmath]k_n < k_{n+1} [/ilmath] so [ilmath]n\le k_n < k_{n+1} [/ilmath] means [ilmath]n<k_{n+1} [/ilmath]
• As [ilmath]k_{n+1} [/ilmath] and [ilmath]n[/ilmath] are integer valued, we can use [ilmath](n<m)\iff(n+1\le m)[/ilmath] for integers [ilmath]n[/ilmath] and [ilmath]m[/ilmath][Note 3]
• Thus we see [ilmath](n<k_{n+1})\iff(n+1\le k_{n+1})[/ilmath], we have the LHS, so now we have the RHS: [ilmath]n+1\le k_{n+1} [/ilmath]
3. Draw conclusions
• Since [ilmath]k_n\ge n[/ilmath] is true for [ilmath]n\eq 1[/ilmath] and if it is true for [ilmath]n\eq m[/ilmath] then it is true for [ilmath]n\eq m+1[/ilmath] we have proved by induction that for all [ilmath]n\in\mathbb{N} [/ilmath] we have [ilmath]k_n\ge n[/ilmath], as required

## Notes

1. Note that strictly increasing cannot be replaced by non-decreasing as the sequence could stay the same (ie a term where [ilmath]m_i\eq m_{i+1} [/ilmath] for example), it didn't decrease, but it didn't increase either. It must be STRICTLY increasing.

If it was simply "non-decreasing" or just "increasing" then we could define: [ilmath]k_n:\eq 5[/ilmath] for all [ilmath]n[/ilmath].
• Then [ilmath](x_{k_n})_{n\in\mathbb{N} } [/ilmath] is a constant sequence where every term is [ilmath]x_5[/ilmath] - the 5th term of [ilmath](x_n)[/ilmath].
2. Some books may simply require increasing, this is wrong. Take the theorem from Equivalent statements to compactness of a metric space which states that a metric space is compact [ilmath]\iff[/ilmath] every sequence contains a convergent subequence. If we only require that:
• [ilmath]k_n\le k_{n+1} [/ilmath]
Then we can define the sequence: [ilmath]k_n:=1[/ilmath]. This defines the subsequence [ilmath]x_1,x_1,x_1,\ldots x_1,\ldots[/ilmath] of [ilmath](x_n)_{n=1}^\infty[/ilmath] which obviously converges. This defeats the purpose of subsequences. A subsequence should preserve the "forwardness" of a sequence, that is for a sub-sequence the terms are seen in the same order they would be seen in the parent sequence, and also the "sub" part means building a sequence from it, we want to built a sequence by choosing terms, suggesting we ought not use terms twice.
The mapping definition directly supports this, as the mapping can be thought of as choosing terms
3. The proof of this is elementary and omitted here. Usually I avoid "exercise for the reader" but they really ought to be able to see it themselves, kids in year 3 can!