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]
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.
- 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 5th term of [ilmath](x_n)[/ilmath].
- ↑ 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!
