Subsequence

Definition

Given a sequence $(x_n)_{n=1}^\infty$ we define a subsequence of $(x_n)^\infty_{n=1}$ as follows:

• Given any strictly increasing monotonic sequence, $(k_n)_{n=1}^\infty\subseteq\mathbb{N}$
  • That means that $\forall n\in\mathbb{N}[k_n<k_{n+1}]$

Then the subsequence of $(x_n)$ given by $(k_n)$ is:

• $(x_{k_n})_{n=1}^\infty$, the sequence whose terms are: $x_{k_1},x_{k_2},\ldots,x_{k_n},\ldots$
  • That is to say the $i$^th element of $(x_{k_n})$ is the $k_i$^th element of $(x_n)$

As a mapping

Consider an (injective) mapping: $k:\mathbb{N}\rightarrow\mathbb{N}$ with the property that:

• $\forall a,b\in\mathbb{N}[a<b\implies k(a)<k(b)]$

This defines a sequence, $(k_n)_{n=1}^\infty$ given by $k_n:= k(n)$

• Now $(x_{k_n})_{n=1}^\infty$ is a subsequence

Immediate properties

[Expand]

$\forall n\in\mathbb{N}[k_n\ge n]$ - the $k_i$^th term of a subsequence cannot correspond to any element before the (but not including) $i$^th term of the main sequence

---

This is a standard proof by induction.

1. Suppose $n\eq 1$, show $k_1\ge 1$
   • Well $k_1$ is the first term of the subsequence and this may be the 1st term of the sequence, in which case we have $k_1\eq 1$ thus $k_1\ge 1$ holds
   • If the first term of the subsequence is any term other than the first we see $k_1>1$ and so $k_1\ge 1$ holds
2. Assuming we have $k_n\ge n$ show that this implies $k_{n+1}\ge n+1$
   • We have $k_n\ge n$ by assumption, and we wish to show $k_n\ge n\implies k_{n+1}\ge n+1$
     • By definition of subsequence we see $k_n < k_{n+1}$ so $n\le k_n < k_{n+1}$ means $n<k_{n+1}$
     • As $k_{n+1}$ and $n$ are integer valued, we can use $(n<m)\iff(n+1\le m)$ for integers $n$ and $m$
     • Thus we see $(n<k_{n+1})\iff(n+1\le k_{n+1})$, we have the LHS, so now we have the RHS: $n+1\le k_{n+1}$
3. Draw conclusions
   • Since $k_n\ge n$ is true for $n\eq 1$ and if it is true for $n\eq m$ then it is true for $n\eq m+1$ we have proved by induction that for all $n\in\mathbb{N}$ we have $k_n\ge n$, as required

See also

• Sequence