# Subsequence

From Maths

## 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]}

- That means that [ilmath]\forall n\in\mathbb{N}[k_n<k_{n+1}][/ilmath]

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]

- That is to say the [ilmath]i[/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.

- 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

- 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]

- 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]
- 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

## See also

## Notes

- ↑ 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 5
^{th}term of [ilmath](x_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 5
- ↑ 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]

The mapping definition directly supports this, as the mapping can be thought of as choosing terms - ↑ 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!