This page is about subsequences of a sequence. A subsequence of a sequence $\left({a}_{n}\right)$ is an infinite collection of numbers from $\left({a}_{n}\right)$ in the same order that they appear in that sequence.

The main theorem on subsequences is that
every subsequence of a convergent sequence $\left({a}_{n}\right)$
converges to the same limit as $\left({a}_{n}\right)$.
This (together with the Theorem on Uniqueness of Limits)
is the main tool in showing a sequence *does not converge*.

It is harder to use subsequences to prove a sequence *does* converge
and much easier to make mistakes in this direction.
Just knowing a sequence $\left({a}_{n}\right)$ has a
convergent subsequence says nothing about the convergence of
$\left({a}_{n}\right)$. We discuss these topics with an example in
another web page.

If $\left({a}_{n}\right)$ is a sequence, such as $\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots $ we may obtain a subsequence by selecting some of the
terms in the sequence. The only rules are that the order
of the terms in the original sequence must be preserved
and we must select an infinite number of terms. For example,
from the above sequence we may select
${b}_{1}={a}_{1}=1$,
${b}_{2}={a}_{2}=\frac{1}{2}$,
${b}_{3}={a}_{4}=\frac{1}{4}$,
${b}_{4}={a}_{8}=\frac{1}{8}$,
and so on. This idea of subsequence

is rather simple
and very natural. Unfortunately there are some difficulties
with notation that tends to obscure the main idea and can make
the manipulation of subsequences a little more tricky.

Definition of subsequence.

Suppose $\left({a}_{n}\right)$ is a sequence and $f:\mathbb{N}\to \mathbb{N}$ is an increasing function (i.e., $\forall n\in \mathbb{N}\forall m\in \mathbb{N}(nm\Rightarrow f\left(n\right)f\left(m\right))$) then $\left({a}_{n}\right)$ and $f$ define a new sequence

with elements

The sequence $\left({b}_{n}\right)$ is called a subsequence of $\left({a}_{n}\right)$.

Example.

For the sequence $\left({a}_{n}\right)$ given by ${a}_{n}=\frac{1}{n}$ we obtain the subsequence ${b}_{n}=\frac{1}{{2}^{n}}$ by taking as our increasing function $f\left(n\right)={2}^{n}$, since ${b}_{n}={a}_{f\left(n\right)}={a}_{{2}^{n}}=\frac{1}{{2}^{n}}$.

The ideas of selecting infinitely many terms from a sequence

and using an increasing function to enumerate a selection of terms
are equivalent. If we have an infinite set of terms we can enumerate
them with a function $f$. Conversely, an increasing function $f$
defines a selection of terms with indices in the image of $f$.
The following lemma is useful in switching between these two views.

Lemma.

Let $f:\mathbb{N}\to \mathbb{N}$ be increasing. Then $f\left(n\right)\u2a7en$ for all $n\in \mathbb{N}$.

**Proof.**

By induction on $n$. Suppose for the sake of this proof that $\mathbb{N}=\left\{0,1,2,3,\dots \right\}$ (a similar argument starting with one works if you prefer $0$ not to be a natural number) and let the induction hypothesis be $f\left(n\right)\u2a7en$. Then $f\left(0\right)\in \mathbb{N}$ and so $f\left(0\right)\u2a7e0$, so the base case is established. Now inductively assume $f\left(n\right)\u2a7en$ and observe that $f\left(n\mathrm{+1}\right)>f\left(n\right)$ as $f$ is increasing. So $f\left(n\mathrm{+1}\right)\u2a7ef\left(n\right)+1\u2a7en+1$ by our hypothesis, and the induction step is proved.

Theorem on Subsequences.

Suppose ${a}_{n}\to l\in \mathbb{R}$ as $n\to \infty $ and $\left({b}_{n}\right)$ is a subsequence of $\left({a}_{n}\right)$ defined by ${b}_{n}={a}_{f\left(n\right)}$. Then ${b}_{n}\to l$ as $n\to \infty $.

**Proof.**

**Subproof.**

Let $\epsilon >0$ be arbitrary.

Let $N\in \mathbb{N}$ satisfy $\forall n\u2a7eN\left|{a}_{n}-l\right|\epsilon $.

**Subproof.**

Let $n\in \mathbb{N}$ be arbitrary.

**Subproof.**

Suppose $n\u2a7eN$.

Then $f\left(n\right)\u2a7en\u2a7eN$ by the lemma.

So $\left|{b}_{n}-l\right|=\left|{a}_{f\left(n\right)}-l\right|<\epsilon $.

So $n\u2a7eN\Rightarrow \left|{b}_{n}-l\right|<\epsilon $.

So $\forall n\in \mathbb{N}(n\u2a7eN\Rightarrow \left|{b}_{n}-l\right|\epsilon )$.

So $\exists N\in \mathbb{N}\forall n\in \mathbb{N}(n\u2a7eN\Rightarrow \left|{b}_{n}-l\right|\epsilon )$.

So $\forall \epsilon >0\exists N\in \mathbb{N}\forall n\in \mathbb{N}(n\u2a7eN\Rightarrow \left|{b}_{n}-l\right|\epsilon )$.

Part of the power of this theorem is that the subsequence $\left({b}_{n}\right)$
converges to *the same* limit. This will be combined with
the Theorem on Uniqueness of Limits
to allow us to prove non-convergence results.

Example.

We use these ideas to re-prove the assertion that the sequence ${a}_{n}={\left(-1\right)}^{n}$ doesn't converge. Define subsequences ${b}_{n}={a}_{2n+1}$ and ${c}_{n}={a}_{2n}$, and observe that ${b}_{n}=-1$ for all $n$ and ${c}_{n}=1$ for all $n$, so ${b}_{n}\to -1$ and ${c}_{n}\to 1$ as $n\to \infty $, as these are constant sequences. Now suppose (to get a contradiction) that $\left({a}_{n}\right)$ converges to some limit $l$. Then by the Theorem on Subsequences both ${b}_{n}\to l$ and ${c}_{n}\to l$ as these are subsequences of $\left({a}_{n}\right)$. By the Theorem on Uniqueness of Limits, $-1=l$ and $1=l$. But this implies $1=-1$ which is false.

Example.

Consider the sequence defined by ${a}_{n}=cos\left(n\right)$. This is proved to be non-convergent as follows.

First a subsequence $\left({b}_{n}\right)$ is selected consisting of all ${a}_{n}$ for which $\exists k\in \mathbb{N}(2k\pi -1n2k\pi +1)$. It may not be immediately obvious that there are infinitely many such $n$ but this is easily proved as for each $k\in \mathbb{N}$ the integer part of $2k\pi $ is such an $n$. Note for such $n$ that $cos\left(n\right)>cos\left(1\right)>0$.

Next a subsequence $\left({c}_{n}\right)$ is selected consisting of all ${a}_{n}$ for which $\exists k\in \mathbb{N}\left(\right(2k+1)\pi -1n(2k+1)\pi +1)$. Again, note that for each $k\in \mathbb{N}$ the integer part of $(2k+1)\pi $ is such an $n$. Note also that for such $n$ that $cos\left(n\right)<-cos\left(1\right)<0$.

Finally, suppose ${a}_{n}\to l\in \mathbb{R}$. Then by the Theorem on Subsequences both ${b}_{n}\to l$ and ${c}_{n}\to l$. But by the Theorem Giving Bounds on Limits we have $l\u2a7ecos\left(1\right)$ as $l$ is the limit of $\left({b}_{n}\right)$. Also $l\u2a7d-cos\left(1\right)$ as $l$ is the limit of $\left({c}_{n}\right)$. But this is impossible as $-cos\left(1\right)<0<cos\left(1\right)$.

Be careful to note the $\u2a7e$ and $\u2a7d$ here! In particular this argument wouldn't have worked if we have simply shown that ${c}_{n}<0<{b}_{n}$ for all $n$ for then it might have been possible that $l=0$.