# Subsequence

(Redirected from Sub-sequence)
Jump to: navigation, search

## Definition

Given a sequence [ilmath](x_n)_{n=1}^\infty[/ilmath] we define a subsequence of [ilmath](x_n)^\infty_{n=1}[/ilmath] 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