Subsequences

1. Introduction

This page is about subsequences of a sequence. A subsequence of a sequence (₎ is an infinite collection of numbers from (₎ in the same order that they appear in that sequence.

The main theorem on subsequences is that every subsequence of a convergent sequence (₎ converges to the same limit as (₎. 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 (₎ has a convergent subsequence says nothing about the convergence of (₎. We discuss these topics with an example in another web page.

2. The Theorem on Subsequences

If (₎ is a sequence, such as 11,12,13,14, 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 _1=₁₌₁, _{2=₂₌₁₂}, _{3=₄₌₁₄}, _{4=₈₌₁₈}, 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 (₎ is a sequence and : is an increasing function (i.e., ( () () ) ) then (₎ and define a new sequence

_=

()

with elements

_1=

(1),_2=

(2),_3=

(3),_4=

(4),

The sequence (₎ is called a subsequence of (₎.

Example.

For the sequence (₎ given by ₌₁ we obtain the subsequence ₌₁₂ by taking as our increasing function ()=2 , since _{=_()
=₂₌₁₂} .

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 . Conversely, an increasing function defines a selection of terms with indices in the image of . The following lemma is useful in switching between these two views.

Lemma.

Let : be increasing. Then () for all .

Proof.

By induction on . Suppose for the sake of this proof that =0,1,2,3, (a similar argument starting with one works if you prefer 0 not to be a natural number) and let the induction hypothesis be () . Then (0) and so (0)0 , so the base case is established. Now inductively assume () and observe that (+1) () as is increasing. So (+1) () +1 +1 by our hypothesis, and the induction step is proved.

Theorem on Subsequences.

Suppose as and (₎ is a subsequence of (₎ defined by _=

(). Then as .

Proof.

Subproof.

Let 0 be arbitrary.

Let satisfy _- .

Subproof.

Let be arbitrary.

Subproof.

Suppose .

Then () by the lemma.

So _-= () - .

So _- .

So ( _- ) .

So 0 ( _- ) .

Part of the power of this theorem is that the subsequence (₎ 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 _=(-1) doesn't converge. Define subsequences _=

2+1 and _=

2 , and observe that _=-1 for all and ₌₁ for all , so _-1 and ₁ as , as these are constant sequences. Now suppose (to get a contradiction) that (₎ converges to some limit . Then by the Theorem on Subsequences both and as these are subsequences of (₎. By the Theorem on Uniqueness of Limits, -1= and 1=. But this implies 1=-1 which is false.

Example.

Consider the sequence defined by ₌₍₎. This is proved to be non-convergent as follows.

First a subsequence (₎ is selected consisting of all for which (2 -1 2 +1) . It may not be immediately obvious that there are infinitely many such but this is easily proved as for each the integer part of 2 is such an . Note for such that () (1)0 .

Next a subsequence ( ₎ is selected consisting of all for which ((2+1)-1 (2+1)+1) . Again, note that for each the integer part of (2+1) is such an . Note also that for such that ()-(1)0 .

Finally, suppose . Then by the Theorem on Subsequences both and . But by the Theorem Giving Bounds on Limits we have (1) as is the limit of (₎. Also -(1) as is the limit of ( ₎ . But this is impossible as -(1)0 (1) .

Be careful to note the and here! In particular this argument wouldn't have worked if we have simply shown that ₀ for all for then it might have been possible that =0.