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
Contents
[hide]Definition
Given a sequence (xn)∞n=1 we define a subsequence of (xn)∞n=1[1][2] as follows:
- Given any strictly increasing monotonic sequence[Note 1], (kn)∞n=1⊆N
- That means that ∀n∈N[kn<kn+1][Note 2]
Then the subsequence of (xn) given by (kn) is:
- (xkn)∞n=1, the sequence whose terms are: xk1,xk2,…,xkn,…
- That is to say the ith element of (xkn) is the kith element of (xn)
As a mapping
Consider an (injective) mapping: k:N→N with the property that:
- ∀a,b∈N[a<b⟹k(a)<k(b)]
This defines a sequence, (kn)∞n=1 given by kn:=k(n)
- Now (xkn)∞n=1 is a subsequence
Immediate properties
[Expand]
∀n∈N[kn≥n] - the kith term of a subsequence cannot correspond to any element before the (but not including) ith term of the main sequence
See also
Notes
- Jump up ↑ Note that strictly increasing cannot be replaced by non-decreasing as the sequence could stay the same (ie a term where mi=mi+1 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: kn:=5 for all n.- Then (xkn)n∈N is a constant sequence where every term is x5 - the 5th term of (xn).
- Jump up ↑ 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 ⟺ every sequence contains a convergent subequence. If we only require that:
- kn≤kn+1
The mapping definition directly supports this, as the mapping can be thought of as choosing terms - Jump up ↑ 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!