Subsequence – Serlo

Introductory Example

Mediendatei abspielen

Einführendes Beispiel zu Teilfolgen (YouTube-Video vom YouTube-Kanal "MJ Education“)

Sometimes its necessary to speak about the "subsequence" of a sequence. Much like a subset is a "part" of a set, a subsequence is some part of a sequence -- all elements of a subsequence are also elements of the original sequence. A subsequence is in end effect constructed by removing some chosen terms of the original sequence. Regardless of how many terms are stripped from the original sequence, the resulting subsequence still has an infinite number of terms. For example, let's take the sequence $a_{n}=(-1)^{n}$:

$-1,\ 1,\ -1,\ 1,\ -1,\ \ldots$

We are interested in a subsequence composed of every other term of the original sequence$a_{n}$. This subsequence arises from either removing all terms with an even index or removing all terms with an odd index. If, for example, we remove all terms with odd index, we get the following schematic:

${\begin{array}{rccccccc}{\text{Originalfolge}}\colon &{\cancel {-1}},\ &{\color {OliveGreen}1},\ &{\cancel {-1}},\ &{\color {OliveGreen}1},&{\cancel {-1}},\ &{\color {OliveGreen}1},\ &\ldots \\{\text{Teilfolge}}\colon &&{\color {OliveGreen}1},\ &&{\color {OliveGreen}1},&&{\color {OliveGreen}1},\ &\ldots \end{array}}$

This gives rise to a subsequence that is constant $1$.

Mathematical Description

Mediendatei abspielen

Erklärung der mathematischen Schreibweise $a_{n_{k}}$ für Teilfolgen (YouTube-Video vom YouTube-Kanal "MJ Education")

How can subsequences be denoted? First let's look at the indices of the sequence terms that we want to keep in the subsequence:

${\begin{array}{rccccccccccccc}{\text{Index }}n\colon &{\cancel {1}}&\ &{\color {RedOrange}2}&\ &{\cancel {3}}&\ &{\color {RedOrange}4}&\ &{\cancel {5}}&\ &{\color {RedOrange}6}&\ &\ldots \\&\downarrow &&\downarrow &&\downarrow &&\downarrow &&\downarrow &&\downarrow &&\\{\text{Folgenglied }}a_{n}\colon &{\cancel {-1}}&\ &{\color {OliveGreen}1}&\ &{\cancel {-1}}&\ &{\color {OliveGreen}1}&\ &{\cancel {-1}}&\ &{\color {OliveGreen}1}&\ &\ldots \end{array}}$

Now we want to find a sequence $\left(n_{k}\right)_{k\in \mathbb {N} }$ that describes these indices. In the above example we consider even indices. So the sequence can be written as $n_{k}=2k$:

${\begin{array}{rccccccccccccc}{\text{Neuer Index }}k\colon &1&\ &2&\ &3&\ &4&\ &\ldots \\[0.5em]&\downarrow &&\downarrow &&\downarrow &&\downarrow &&\\[0.5em]{\text{Indexfolge }}n_{k}\colon &{\color {RedOrange}2}&\ &{\color {RedOrange}4}&\ &{\color {RedOrange}6}&\ &{\color {RedOrange}8}&\ &\ldots \end{array}}$

We substitute this sequence into $\left(a_{n}\right)_{n\in \mathbb {N} }$. From there we get the subsequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$:

${\begin{array}{rccccccccccccc}{\text{Neuer Index }}k\colon &1&&2&&3&&\ldots \\[0.5em]&\downarrow &&\downarrow &&\downarrow &&\\[0.5em]{\text{Indexfolge }}n_{k}\colon &{\color {RedOrange}2}&&{\color {RedOrange}4}&&{\color {RedOrange}6}&&\ldots \\[0.5em]&\downarrow &&\downarrow &&\downarrow &&\\[0.5em]{\text{Teilfolge }}a_{n_{k}}\colon &{\color {OliveGreen}(-1)^{2}=1}&&{\color {OliveGreen}(-1)^{4}=1}&&{\color {OliveGreen}(-1)^{6}=1}&&\ldots \end{array}}$

First we will build the sequence $\left(n_{k}\right)_{k\in \mathbb {N} }$ of relevant indices of the subsequence. We will set this subsequence into the original sequence $\left(a_{n}\right)_{n\in \mathbb {N} }$ for $n$ so that we get the sequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$.

In our example we have ${\color {RedOrange}n_{k}=2k}$. So we substitute ${\color {RedOrange}2k}$ for $n$ in $a_{n}=(-1)^{n}$. Then we obtain the subsequence ${\color {OliveGreen}a_{2k}=(-1)^{2k}=1}$.

Definition

Mediendatei abspielen

Definition von Teilfolgen (YouTube-Video from YouTube-Kanal: "MJ Education")

Definition (Subsequence)

Let $\left(a_{n}\right)_{n\in \mathbb {N} }$ be an arbitrary sequence. Any sequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ is called a subsequence of $\left(a_{n}\right)_{n\in \mathbb {N} }$ if $\left(n_{k}\right)_{k\in \mathbb {N} }$ is a strictly monotone increasing sequence of natural numbers.

This concept is important for analysis since it is used to characterize so-called "limit points." However, these will not be properly defined and discussed until the next chapter.

Hint

Every sequence is a subsequence of itself. Namely, if one chooses $n_{k}=k$, then $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }=\left(a_{k}\right)_{k\in \mathbb {N} }=\left(a_{n}\right)_{n\in \mathbb {N} }$. For $n_{k}=k$ the subsequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ is identical to the original sequence $\left(a_{n}\right)_{n\in \mathbb {N} }$. This shows that every sequence is a subsequence of itself.

Exercise (Subsequences)

Find five different subsequences of the sequence $\left({\tfrac {1}{n}}\right)_{n\in \mathbb {N} }$.

Solution (Subsequences)

The sequence $\left({\tfrac {1}{n}}\right)_{n\in \mathbb {N} }$ has infinitely many subsequences. Five examples would be

${\begin{aligned}\left({\tfrac {1}{2k}}\right)_{k\in \mathbb {N} }&=\left({\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {1}{6}},{\tfrac {1}{8}},{\tfrac {1}{10}},\ldots \right)\\\left({\tfrac {1}{2k-1}}\right)_{k\in \mathbb {N} }&=\left({\tfrac {1}{1}},{\tfrac {1}{3}},{\tfrac {1}{5}},{\tfrac {1}{7}},{\tfrac {1}{9}},\ldots \right)\\\left({\tfrac {1}{k^{2}}}\right)_{k\in \mathbb {N} }&=\left({\tfrac {1}{1}},{\tfrac {1}{4}},{\tfrac {1}{9}},{\tfrac {1}{16}},{\tfrac {1}{25}},\ldots \right)\\\left({\tfrac {1}{k+2}}\right)_{k\in \mathbb {N} }&=\left({\tfrac {1}{3}},{\tfrac {1}{4}},{\tfrac {1}{5}},{\tfrac {1}{6}},{\tfrac {1}{7}},\ldots \right)\\\left({\tfrac {1}{p(k)}}\right)_{k\in \mathbb {N} }&=\left({\tfrac {1}{2}},{\tfrac {1}{3}},{\tfrac {1}{5}},{\tfrac {1}{7}},{\tfrac {1}{11}},\ldots \right),{\text{ wobei }}p(k){\text{ die }}k{\text{-te Primzahl ist}}\end{aligned}}$

Convergence of Subsequences

For subsequences we have the following important theorem:

Theorem (Convergence of Subsequences)

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence. It converges if and only if every subsequence converges. The limit of the sequence coincides with the limits of the subsequences.

Proof (Convergence of Subsequences)

To prove the equivalence

${\begin{array}{c}(a_{n})_{n\,\in \,\mathbb {N} }{\text{ converges to }}a\\[1ex]\iff \\[1ex]{\text{Every subsequence of }}(a_{n})_{n\in \mathbb {N} }{\text{ converges to }}a\end{array}}$

we have to prove the following two implications:

1. If $(a_{n})_{n\in \mathbb {N} }$ converges to $a$, then every subsequence of $(a_{n})_{n\in \mathbb {N} }$ converges to $a$, as well.
2. If every subsequence of $(a_{n})_{n\in \mathbb {N} }$ converges to $a$, then $(a_{n})_{n\in \mathbb {N} }$ converges to $a$, as well.

We can split the proof into these two parts, since the statement $A\iff B$ is equivalent to the two implications $(A\implies B)\land (B\implies A)$.

Proof step: Convergence of the sequence implicates the convergence of all subsequences - to the same limit.

Let $(a_{n})_{n\in \mathbb {N} }$ be a sequence converging to $a$.Now, we need to prove that all subsequences of $(a_{n})_{n\in \mathbb {N} }$converge to $a$, as well.

So, let $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ be a subseqeunce of $(a_{n})_{n\in \mathbb {N} }$. We would like to show that $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ converges to $a$ . Let $\epsilon >0$ be given arbitrarily. Since $a$ is the limit of $(a_{n})_{n\in \mathbb {N} }$ , there must be an index $N\in \mathbb {N}$, such that for all $n\geq N$ the inequality $|a_{n}-a|<\epsilon$ holds.

Since the sequence $(n_{k})_{k\in \mathbb {N} }$ is by definition strictly decreasing , there will be $n_{k}\geq k$ for all $k\in \mathbb {N}$. Therefore, $n_{k}\geq N$ for all $k\geq N$, since from $n_{k}\geq k$ and $k\geq N$ we conclude $n_{k}\geq k\geq N$. Hence, there is also $\left|a_{n_{k}}-a\right|<\epsilon$ for all $k\geq N$.

We have just proven that for any given $\epsilon >0$ there is an $N\in \mathbb {N}$ with $\left|a_{n_{k}}-a\right|<\epsilon$ for all $k\geq N$ . But this is just the definition for " $(a_{n_{k}})_{k\in \mathbb {N} }$ converges to $a$" . Since any subsequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ can be chosen in this place, the proof holds for all subsequences of $(a_{n})_{n\in \mathbb {N} }$.

Proof step: Convergence of all subsequences to the same limit implies convergence of the sequence.

We know that all subsequences of $(a_{n})_{n\in \mathbb {N} }$ converge to $a$ . But now, the sequence $(a_{n})_{n\in \mathbb {N} }$ is a subsequence of itself (just set $n_{k}=k$). So the sequence itself must also converge to $a$ .

Example (Convergence of subsequences)

Since $(a_{n})_{n\in \mathbb {N} }=\left({\tfrac {1}{n}}\right)_{n\in \mathbb {N} }$ is a null sequence, the same will hold for the two limits

${\begin{aligned}\lim _{k\to \infty }a_{2k}&=\lim _{k\to \infty }{\tfrac {1}{2k}}=0\\\lim _{k\to \infty }a_{2k-1}&=\lim _{k\to \infty }{\tfrac {1}{2k-1}}=0\end{aligned}}$

Hint

The above theorem directly implies that a convergent sequence $(a_{n})_{n\in \mathbb {N} }$ does not change its limit, if a finite number of elements are canceled. Removing a finite amount of elements will render a subsequence $(a_{n_{k}})_{k\in \mathbb {N} }$ of $(a_{n})_{n\in \mathbb {N} }$. And we just showed that the limits of those two sequences coincide.

The above theorem directly implies:

Theorem (Divergence in case of a diverging subsequence)

If a subsequence diverges, the original sequence must also diverge.

Check your understanding: Why does the above theorem imply that the original sequence has to diverge, if any subsequence does so?

We know: If a sequence converges, then all of its subsequences also have to diverge. If there was a convergent sequence for which we could find a divergent subsequence, we would have a contradiction to the theorem. So if a subsequence diverges, we know that the original sequence must have been convergent.

Example (DDivergence of subsequences)

Let us consider the sequence $(a_{n})_{n\in \mathbb {N} }$ with $a_{n}=(-1)^{n}n$. A subsequence is obtained by selecting only the positive elements, which are $(a_{2k})_{k\in \mathbb {N} }=(2k)_{k\in \mathbb {N} }$ . Since $(2k)_{k\in \mathbb {N} }$ is an unbounded sequence, it diverges. Therefore, the original sequence $(a_{n})_{n\in \mathbb {N} }$ must also diverge.

Application: convergence of mixed sequences

In the chapter „Beispiele und Eigenschaften von Folgen“ we have seen how to compose to sequences $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ to a "mixed sequence" $(a_{n})_{n\in \mathbb {N} }$ . This mixture is defined as

$a_{n}={\begin{cases}b_{\frac {n+1}{2}}&{\text{for }}n{\text{ odd}}\\c_{\frac {n}{2}}&{\text{for }}n{\text{ even}}\end{cases}}$

That means, the sequence $(a_{n})_{n\in \mathbb {N} }$ is composed out of the two subsequences $(a_{2n-1})_{n\in \mathbb {N} }=(b_{n})_{n\in \mathbb {N} }$ and $(a_{2n})_{n\in \mathbb {N} }=(c_{n})_{n\in \mathbb {N} }$ .

We may now ask how the convergence of the mixture $(a_{n})_{n\in \mathbb {N} }$ relates to the convergences of its two constituents $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ . In order for $(a_{n})_{n\in \mathbb {N} }$ to converge, two conditions must be satisfied:

• First, both subsequences $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ have to converge, as we know that for convergent sequences, all subsequences converge.
• Second, the limits of $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ must be identical. This is because if $(a_{n})_{n\in \mathbb {N} }$ converges, then all of its subsequences must tend to the same limit.

If one of these two conditions is not satisfied, the mixed sequence $(a_{n})_{n\in \mathbb {N} }$ must diverge. But are the two conditions also sufficient for convergence of the mixed sequence? Indeed, they are! We will now proof this. The limit of the mixed sequence must the coincide with the two limits of the subsequences.

Theorem (Convergence of mixed sequences)

Let $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ be two sequences and $a\in \mathbb {R}$ a limit candidate. Let the mixed sequence $(a_{n})_{n\in \mathbb {N} }$ be defined by

$a_{n}={\begin{cases}b_{\frac {n+1}{2}}&{\text{for }}n{\text{ odd}}\\c_{\frac {n}{2}}&{\text{for }}n{\text{ even}}\end{cases}}$

. It converges to $a$, if and only if the sequences $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ both converge to $a$ .

Proof (Convergence of mixed sequences)

Proof step: If $(a_{n})_{n\in \mathbb {N} }$ converges to $a$ , then both $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ converge to $a$.

As $(b_{n})_{n\in \mathbb {N} }=(a_{2n-1})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }=(a_{2n})_{n\in \mathbb {N} }$ , both $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ are subsequences of $(a_{n})_{n\in \mathbb {N} }$. Since $(a_{n})_{n\in \mathbb {N} }$ converges to $a$ , all of its subsequences will do so, too. This specifically includes $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ , which hence converge to $a$.

Proof step: If both $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ converge to $a$ , then also $(a_{n})_{n\in \mathbb {N} }$ converges to $a$.

As both $(b_{n})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }$ converge to $a$ , the following two statements hold:

• $\forall \epsilon >0\,\exists N_{1}\in \mathbb {N} \,\forall n\geq N_{1}:|b_{n}-a|<\epsilon$
• $\forall \epsilon >0\,\exists N_{2}\in \mathbb {N} \,\forall n\geq N_{2}:|c_{n}-a|<\epsilon$

Since $(b_{n})_{n\in \mathbb {N} }=(a_{2n-1})_{n\in \mathbb {N} }$ and $(c_{n})_{n\in \mathbb {N} }=(a_{2n})_{n\in \mathbb {N} }$ there is:

• $\forall \epsilon >0\,\exists N_{1}\in \mathbb {N} \,\forall n\geq N_{1}:|a_{2n-1}-a|<\epsilon$
• $\forall \epsilon >0\,\exists N_{2}\in \mathbb {N} \,\forall n\geq N_{2}:|a_{2n}-a|<\epsilon$

Let now $\epsilon >0$ be given arbitrarily. The above statements imply that there is a threshold number $N_{1}$ (for b) with $|a_{2n-1}-a|<\epsilon$ for all $n\geq N_{1}$. In addition, there is a threshold $N_{2}$ (for c) with $|a_{2n}-a|<\epsilon$ for all $n\geq N_{2}$. We choose the maximum of both thresholds $N=\max\{2N_{1}-1,2N_{2}\}$. Let $m\geq N$ be a number above this threshold. If $m$ is odd, then $m=2n-1$ for some $n\in \mathbb {N}$. Since $m\geq 2N_{1}-1$, there is especially $n\geq N_{1}$ and hence

$|a_{m}-a|=|a_{2n-1}-a|<\epsilon$

In case $m$ is even, we know that $m=2n$ for some $n\in \mathbb {N}$. As $m\geq 2N_{2}$ , there is $n\geq N_{2}$ and therefore

$|a_{m}-a|=|a_{2n}-a|<\epsilon$

In any case, $|a_{m}-a|<\epsilon$ for all $m\in \mathbb {N}$. This establishes convergence $\lim _{m\to \infty }a_{m}=a$.

Check your understanding: In the above proof, we chose $N=\max\{2N_{1}-1,2N_{2}\}$ . Why couldn't we have chosen $N=\max\{N_{1},N_{2}\}$ ?

In the above proof, we used that $|a_{2n-1}-a|<\epsilon$ for all $n\geq N_{1}$ . This means, starting from a sequence element $a_{2N_{1}-1}$ , all odd elements $(a_{m})_{m\in \mathbb {N} }$ will satisfy the inequality $|a_{m}-a|<\epsilon$ . Analogously, $|a_{2n}-a|<\epsilon$ for all $n\geq N_{2}$ implies that starting from a sequence element $a_{2N_{2}}$ all even elements $(a_{m})_{m\in \mathbb {N} }$ will satisfy the inequality $|a_{m}-a|<\epsilon$ . I order to prove $|a_{m}-a|<\epsilon$ , we therefore need $m\geq 2N_{1}-1$ and $m\geq 2N_{2}$. Hence, we choose $N=\max\{2N_{1}-1,2N_{2}\}$, so $m\geq N$ both ensures $m\geq 2N_{1}-1$ and $m\geq 2N_{2}$ .

Example (Convergence of mixed sequences)

Consider the mixed sequence $(a_{n})_{n\in \mathbb {N} }$ with $a_{n}=(-1)^{n}{\tfrac {1}{n}}$. This can be considered a mixed sequence with

$a_{n}=(-1)^{n}{\frac {1}{n}}={\begin{cases}-{\frac {1}{n}}&{\text{ for }}n{\text{: even}}\\{\frac {1}{n}}&{\text{ for }}n{\text{: odd}}\end{cases}}$

The two constituents of $(a_{n})_{n\in \mathbb {N} }$ are the subsequences $b_{n}=a_{2n-1}=-{\tfrac {1}{2n-1}}$ and $c_{n}=a_{2n}={\frac {1}{2n}}$. Now

${\begin{aligned}\lim _{n\to \infty }b_{n}&=\lim _{n\to \infty }-{\frac {1}{2n-1}}=0\\\lim _{n\to \infty }c_{n}&=\lim _{n\to \infty }{\frac {1}{2n}}=0\end{aligned}}$

Both subsequences converge to zero. For the above theorem, the mixed sequence $(a_{n})_{n\in \mathbb {N} }$ must therefore also converge to zero.