Difference between revisions of "Subsequence"
From Maths
(Created page with "==Definition== {{:Subsequence/Definition}} ==See also== * Sequence ==Notes== <references group="Note"/> ==References== <references/> {{Definitio...") |
(Added useful lemma) |
||
| Line 1: | Line 1: | ||
==[[Subsequence/Definition|Definition]]== | ==[[Subsequence/Definition|Definition]]== | ||
{{:Subsequence/Definition}} | {{:Subsequence/Definition}} | ||
| + | ==Immediate properties== | ||
| + | {{Begin Inline Theorem}} | ||
| + | {{M|1=\forall n\in\mathbb{N}[k_n\ge n]}} - the {{M|k_i}}<sup>th</sup> term of a subsequence cannot correspond to any element before the (but not including) {{M|i}}<sup>th</sup> term of the main sequence | ||
| + | {{Begin Inline Proof}} | ||
| + | This is a standard [[proof by induction]]. | ||
| + | # Suppose {{M|n\eq 1}}, show {{M|k_1\ge 1}} | ||
| + | #* Well {{M|k_1}} is the first term of the subsequence and this may be the 1st term of the sequence, in which case we have {{M|k_1\eq 1}} thus {{M|k_1\ge 1}} holds | ||
| + | #* If the first term of the subsequence is any term other than the first we see {{M|k_1>1}} and so {{M|k_1\ge 1}} holds | ||
| + | # Assuming we have {{M|k_n\ge n}} show that this [[implies]] {{M|k_{n+1}\ge n+1}} | ||
| + | #* We have {{M|k_n\ge n}} by assumption, and we wish to show {{M|k_n\ge n\implies k_{n+1}\ge n+1}} | ||
| + | #** By definition of subsequence we see {{M|k_n < k_{n+1} }} so {{M|n\le k_n < k_{n+1} }} means {{M|n<k_{n+1} }} | ||
| + | #** As {{M|k_{n+1} }} and {{M|n}} are integer valued, we can use {{M|(n<m)\iff(n+1\le m)}} for integers {{M|n}} and {{M|m}}<ref group="Note">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!</ref> | ||
| + | #** Thus we see {{M|(n<k_{n+1})\iff(n+1\le k_{n+1})}}, we have the LHS, so now we have the RHS: {{M|n+1\le k_{n+1} }} | ||
| + | # Draw conclusions | ||
| + | #* Since {{M|k_n\ge n}} is true for {{M|n\eq 1}} and if it is true for {{M|n\eq m}} then it is true for {{M|n\eq m+1}} we have proved by induction that for all {{M|n\in\mathbb{N} }} we have {{M|k_n\ge n}}, as required | ||
| + | {{End Proof}}{{End Theorem}} | ||
==See also== | ==See also== | ||
* [[Sequence]] | * [[Sequence]] | ||
Latest revision as of 23:27, 16 November 2016
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!
