Difference between revisions of "Real Numbers:Sequences"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
 
(8 intermediate revisions by 2 users not shown)
Line 81: Line 81:
 
|}
 
|}
  
==Convergence==
+
==Convergence and Limits==
 
A further important property of sequences (arguably the most important property from the perspective of analysis) is the property of convergence. This property can be easily described by extending the epsilon-delta definition. However, because sequences are relative to counting numbers, there exists an additional way to imagine convergence. Both methods are described below.
 
A further important property of sequences (arguably the most important property from the perspective of analysis) is the property of convergence. This property can be easily described by extending the epsilon-delta definition. However, because sequences are relative to counting numbers, there exists an additional way to imagine convergence. Both methods are described below.
  
Line 158: Line 158:
 
# If ''x''<sub>n</sub>&nbsp;&le;&nbsp;''y''<sub>n</sub> for every ''n'' in ''N'', then <math>\lim_{n\to\infty}x_n \leq \lim_{n\to\infty}y_n</math>.
 
# If ''x''<sub>n</sub>&nbsp;&le;&nbsp;''y''<sub>n</sub> for every ''n'' in ''N'', then <math>\lim_{n\to\infty}x_n \leq \lim_{n\to\infty}y_n</math>.
 
====Proof====
 
====Proof====
1. Let ''x''=lim&nbsp;''x''<sub>''n''</sub> and ''y''=lim&nbsp;''y''<sub>''n''</sub>.  We need to show that for any ε&gt;0 there is natural number ''N'' so that if ''n''&ge; ''N'', then |(''x''<sub>''n''</sub>&nbsp;+&nbsp;''y''<sub>''n''</sub>)&nbsp;&minus;&nbsp;(''x''&nbsp;+&nbsp;''y'')|&le;ε. Given any ε&gt;0 we have ε/3&gt;0 so from the [[Real analysis/Sequences#Convergence|definition of convergence]] there is a natural number ''N''<sub>''x''</sub> so that |''x''<sub>''n''</sub>&minus;''x''|&le;ε/3 for all ''n''&gt;''N''<sub>''x''</sub>, similarly we can choose ''N''<sub>''y''</sub> |''y''<sub>''n''</sub>&minus;''y''|&le;ε/3 for all ''n''&gt;''N''<sub>''y''</sub>.
+
1. Let ''x''=lim&nbsp;''x''<sub>''n''</sub> and ''y''=lim&nbsp;''y''<sub>''n''</sub>.  We need to show that for any ε&gt;0 there is natural number ''N'' so that if ''n''&ge; ''N'', then |(''x''<sub>''n''</sub>&nbsp;+&nbsp;''y''<sub>''n''</sub>)&nbsp;&minus;&nbsp;(''x''&nbsp;+&nbsp;''y'')|&le;ε. Given any ε&gt;0 we have ε/3&gt;0 so from the definition of convergence there is a natural number ''N''<sub>''x''</sub> so that |''x''<sub>''n''</sub>&minus;''x''|&le;ε/3 for all ''n''&gt;''N''<sub>''x''</sub>, similarly we can choose ''N''<sub>''y''</sub> |''y''<sub>''n''</sub>&minus;''y''|&le;ε/3 for all ''n''&gt;''N''<sub>''y''</sub>.
  
 
Let ''N''=max(''N''<sub>x</sub> ,''N''<sub>y</sub>).  If ''n''&gt;''N'', then by the triangle inequality we have
 
Let ''N''=max(''N''<sub>x</sub> ,''N''<sub>y</sub>).  If ''n''&gt;''N'', then by the triangle inequality we have
Line 272: Line 272:
  
 
These theorems all describe different aspects of the completeness of the real numbers.  The reader will notice that the least upper bound property was used heavily in this section, and it is the axiom that separates the real numbers from the rational numbers.  While these theorems would be false for the rational numbers, not all of them can substitute for the least upper bound property.  The Cauchy criterion and the nested intervals property are not strong enough to imply the least upper bound property without additional assumptions, while the Convergence of Monotone sequences theorem and the Bolzano&mdash;Weierstrass property do imply the least upper bound property.
 
These theorems all describe different aspects of the completeness of the real numbers.  The reader will notice that the least upper bound property was used heavily in this section, and it is the axiom that separates the real numbers from the rational numbers.  While these theorems would be false for the rational numbers, not all of them can substitute for the least upper bound property.  The Cauchy criterion and the nested intervals property are not strong enough to imply the least upper bound property without additional assumptions, while the Convergence of Monotone sequences theorem and the Bolzano&mdash;Weierstrass property do imply the least upper bound property.
 +
 +
===Contractive Sequence (Definition)===
 +
A sequence of real numbers <math> (x_n) </math> is '''contractive''' if there exists some constant <math>k</math>, <math>0 < k < 1</math>, such that
 +
 +
: <math> |x_{n+2} - x_{n+1}| \leq k|x_{n+1} - x_{n}| </math>
 +
 +
for all <math>n\in\N</math>.
 +
 +
Every contractive sequence is also a Cauchy sequence (this proof is left to the reader as an exercise), and thus every contractive sequence is convergent by the Cauchy Criterion. However, note that this does not mean that every Cauchy sequence is contractive. The reader is encouraged to find a counterexample to prove this statement (that is, find a sequence that is convergent, and thus Cauchy, that is NOT contractive).
  
 
==Limit superior and limit inferior==
 
==Limit superior and limit inferior==
Line 321: Line 330:
 
:<math>-\epsilon \leq x-x_n\leq \epsilon.\quad\Box</math>
 
:<math>-\epsilon \leq x-x_n\leq \epsilon.\quad\Box</math>
  
==Resources==
+
==The Tail of a Sequence of Real Numbers==
* [https://en.wikibooks.org/wiki/Real_Analysis/Sequences Sequences], Wikibooks: Real Analysis
+
We will now look at an important aspect of a sequence known as the tail of a sequence.
 +
 
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
'''Definition:''' Let <math>(a_n) = (a_1, a_2, ... )</math> be a sequence of real numbers. Then for any <math>m \in \mathbb{N}</math>, the <strong><math>m</math>-Tail</strong> of <math>(a_n)</math> is a the subsequence <math>(a_{m+1}, a_{m+2}, ... ) = (a_{m+n} : n \in \mathbb{N})</math>.
 +
</blockquote>
 +
 
 +
Recall that for a sequence <math>(a_n)_{n=1}^{\infty}</math> that converges to the real number <math>L</math> then <math>\lim_{n \to \infty} a_n = L</math>, that is <math>\forall \varepsilon > 0</math> there exists a natural number <math>n \in \mathbb{N}</math> such that if <math>n \geq N</math> then <math>\mid a_n - L \mid < \varepsilon</math>. For any given positive <math>\varepsilon</math> we can consider the <math>n</math>-tail of the sequence <math>(a_n)</math> to be the subsequence of <math>(a_n)</math> such that all terms in this tail are within an <math>\varepsilon</math>-distance from our limit <math>L</math>. The diagram below illustrates this concept.
 +
 
 +
<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">[http://mathonline.wdfiles.com/local--files/the-tail-of-a-sequence-of-real-numbers/Screen%20Shot%202014-10-13%20at%202.27.28%20AM.png '''''The Tail of a Sequence of Real Numbers''''']</div>
 +
 
 +
The following theorem tells us that the m-tail of a sequence must also converge to the limit <math>L</math> provided the parent sequence <math>(a_n)</math> converges to <math>L</math>.
 +
 
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
'''Theorem 1:''' Let <math>(a_n)</math> be a sequence of real numbers. Then <math>(a_n)</math> converges to <math>L</math> if and only if for any <math>m \in \mathbb{N}</math> the <math>m</math>-tail of <math>(a_n)</math>, call it <math>(a_{n_k})</math> converges to <math>L</math>.
 +
</blockquote>
 +
 
 +
==Subsequence==
 +
In mathematics, a '''subsequence''' of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence <math>\langle A,B,D \rangle</math> is a subsequence of <math>\langle A,B,C,D,E,F \rangle</math> obtained after removal of elements <math>C,</math> <math>E,</math> and <math>F.</math> The relation of one sequence being the subsequence of another is a preorder.
 +
 
 +
Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as <math>\langle B,C,D \rangle,</math> from <math>\langle A,B,C,D,E,F \rangle,</math> is a substring. The substring is a refinement of the subsequence.
 +
 
 +
The list of all subsequences for the word "'''apple'''" would be "''a''", "''ap''", "''al''", "''ae''", "''app''", "''apl''", "''ape''", "''ale''", "''appl''", "''appe''", "''aple''", "''apple''", "''p''", "''pp''", "''pl''", "''pe''", "''ppl''", "''ppe''", "''ple''", "''pple''", "''l''", "''le''", "''e''", "" (empty string).
 +
 
 +
=== Common subsequence ===
 +
 
 +
Given two sequences <math>X</math> and <math>Y,</math> a sequence <math>Z</math> is said to be a ''common subsequence'' of <math>X</math> and <math>Y,</math> if <math>Z</math> is a subsequence of both <math>X</math> and <math>Y.</math>  For example, if
 +
<math display=block>X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle \qquad \text{ and}</math>
 +
<math display=block>Y = \langle B,E,G,J,C,F,E,K,B \rangle \qquad \text{ and}</math>
 +
<math display=block>Z = \langle B,E,E \rangle.</math>
 +
then <math>Z</math> is said to be a common subsequence of <math>X</math> and <math>Y.</math>
 +
 
 +
This would ''not'' be the ''longest common subsequence'', since <math>Z</math> only has length 3, and the common subsequence <math>\langle B,E,E,B \rangle</math> has length&nbsp;4. The longest common subsequence of <math>X</math> and <math>Y</math> is <math>\langle B,E,G,C,E,B \rangle.</math>
 +
 
 +
=== Applications ===
 +
 
 +
Subsequences have applications to computer science, especially in the discipline of bioinformatics, where computers are used to compare, analyze, and store DNA, RNA, and protein sequences.
 +
 
 +
Take two sequences of DNA containing 37 elements, say:
 +
 
 +
:<tt>SEQ<sub>1</sub> = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA</tt>
 +
:<tt>SEQ<sub>2</sub> = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA</tt>
 +
 
 +
The longest common subsequence of sequences 1 and 2 is:
 +
 
 +
:<tt>LCS<sub>(SEQ<sub>1</sub>,SEQ<sub>2</sub>)</sub> = '''CGTTCGGCTATGCTTCTACTTATTCTA'''</tt>
 +
 
 +
This can be illustrated by highlighting the 27 elements of the longest common subsequence into the initial sequences:
 +
 
 +
:<tt>SEQ<sub>1</sub> = A<span style="color:#FF3399">CG</span>G<span style="color:#FF3399">T</span>G<span style="color:#FF3399">TCG</span>T<span style="color:#FF3399">GCTATGCT</span>GA<span style="color:#FF3399">T</span>G<span style="color:#FF3399">CT</span>G<span style="color:#FF3399">ACTTAT</span>A<span style="color:#FF3399">T</span>G<span style="color:#FF3399">CTA</span></tt>
 +
:<tt>SEQ<sub>2</sub> = <span style="color:#FF3399">CGTTCGGCTAT</span>C<span style="color:#FF3399">G</span>TA<span style="color:#FF3399">C</span>G<span style="color:#FF3399">TTCTA</span>TT<span style="color:#FF3399">CT</span>A<span style="color:#FF3399">T</span>G<span style="color:#FF3399">ATT</span>T<span style="color:#FF3399">CTA</span>A </tt>
 +
 
 +
Another way to show this is to ''align'' the two sequences, that is, to position elements of the longest common subsequence in a same column (indicated by the vertical bar) and to introduce a special character (here, a dash) for padding of arisen empty subsequences:
 +
:<tt>SEQ<sub>1</sub> = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-</tt>
 +
:<tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;||&nbsp;|||&nbsp;|||||&nbsp;|&nbsp;&nbsp;|&nbsp;|&nbsp;&nbsp;|&nbsp;||&nbsp;|&nbsp;&nbsp;||&nbsp;|&nbsp;||&nbsp;|&nbsp;&nbsp;||| </tt>
 +
:<tt>SEQ<sub>2</sub> = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA</tt>
 +
 
 +
Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine.
 +
 
 +
=== Theorems ===
 +
 
 +
* Every infinite sequence of real numbers has an infinite monotone subsequence (This is a lemma used in the proof of the Bolzano–Weierstrass theorem).
 +
* Every infinite bounded sequence in <math>\R^n</math> has a convergent subsequence (This is the Bolzano–Weierstrass theorem).
 +
* For all integers <math>r</math> and <math>s,</math> every finite sequence of length at least <math>(r - 1)(s - 1) + 1</math> contains a monotonically increasing subsequence of length&nbsp;<math>r</math> ''or'' a monotonically decreasing subsequence of length&nbsp;<math>s</math> (This is the Erdős–Szekeres theorem).
 +
 
 +
== Licensing ==
 +
Content obtained and/or adapted from:
 +
* [https://en.wikibooks.org/wiki/Real_Analysis/Sequences Sequences, Wikibooks: Real Analysis] under a CC BY-SA license
 +
* [https://en.wikipedia.org/wiki/Subsequence Subsequence, Wikipedia] under a CC BY-SA license
 +
* [http://mathonline.wikidot.com/the-tail-of-a-sequence-of-real-numbers The Tail of a Sequence of Real Numbers, mathonline.wikidot.com] under a CC BY-SA license

Latest revision as of 13:21, 11 November 2021

Definition

Sequences occur frequently in analysis, and they appear in many contexts. While we are all familiar with sequences, it is useful to have a formal definition.

Definition A sequence of real numbers is any function a : NR.

Often sequences such as these are called real sequences, sequences of real numbers or sequences in R to make it clear that the elements of the sequence are real numbers. Analogous definitions can be given for sequences of natural numbers, integers, etc.

Given a sequence (xn), a subsequence, notated as , is a sequence where (nj) is strictly increasing sequence of natural numbers.

For example, taking nj=2j would the subsequence consisting of every other element of the original sequence, that is (x2x4x6, …).

Sequence Notation

However, we usually write an for the image of n under a, rather than a(n). The values an are often called the elements of the sequence. To make a distinction between a sequence and one of its values it is often useful to denote the entire sequence by , or just (an). Some employ set notation and denote it as {an} When specifying a particular sequence, it may be written in the form (a1, a2, a3, …), when the sequence is infinite, or (a1, a2, …, an) when the sequence is finite. We tend only to discretely write down enough elements is so that the pattern is clear, which is typically 3 times.

Examples of Sequences

(1, 2, 3, 4, …), (1, -2, 3, -4, …), and (1, π, π2, π3, π4, …) are all examples of sequences. Note, however, that there need not be any particular pattern to the elements of the sequence. For example, we may specify an to be the n-th digit of π. Often sequences are defined recursively. That is, to specify some initial values of the sequence, and then to specify how to get the next element of the sequence from the previous elements. For example, consider the sequence x1=1, x2=1, and xn = xn−1 + xn−2 for n ≥ 3. This sequences is known as the Fibonacci sequence, and its first few terms are given by (1, 1, 2, 3, 5, 8, 13, …). Another familiar example of a recursive sequence is Newton's method. With an initial guess x0 for the zero of a function, Newton's method tells you how to construct the next guess. In this way you generate a sequence which (hopefully) converges to the zero of the function.

Operations on Sequences

We can also perform algebraic operations on sequences. In other words, we can add, subtract, multiply, divide sequences. These operations are simply performed element by element, for completeness we give the definitions.

Definition Given two sequences (xn) and (yn) and a real number c, we define the following operations:
Sequence operators
Operator Definition Property
Addition (xn) + (yn) (xn + yn)
Subtraction (xn) − (yn) (xnyn)
Multiplication (xn) ⋅ (yn) (xnyn)
Division (xn) ⁄ (yn) (xn/yn), if yn ≠ 0 for all n in N
Scalar c ⋅ (xn) (cxn)

Classification of Sequences

An example of a monotonic non-decreasing function
An example of a monotonic non-increasing function
An example of a non-monotonic function

Some properties of sequence are so important that they are given special names.

Different types of monotone sequences
Definition Property
strictly increasing if an < an+1 for all n in N
non-decreasing if an ≤ an+1 for all n in N
strictly decreasing if an > an+1 for all n in N
non-increasing if an ≥ an+1 for all n in N
Definition Property
monotone if it satisfies any above definition for all n in N
strictly monotone if it is either strictly increasing or strictly decreasing;


Some of these terms are prefixed with strictly because the term increasing is used in some contexts with meaning either that of strictly increasing or of non-decreasing, and similarly decreasing can mean the same as either strictly decreasing, or non-increasing. As a result, these ambiguous terms are usually prefixed with and strictly. We will try adhere to using this unambiguous term.

From here, we will also describe properties of sequences based on boundedness, a word which we will define for sequences below.

Different types of boundedness
Definition Property
bounded above if there exists M in R such that an<M for all n in N
bounded below if there exists M in R such that an>M for all n in N
bounded if the sequence is both bounded above and bounded below
Cauchy if for all ε>0 there exists a natural number N so that, for all n, m > N, |am-an| < ε

Convergence and Limits

A further important property of sequences (arguably the most important property from the perspective of analysis) is the property of convergence. This property can be easily described by extending the epsilon-delta definition. However, because sequences are relative to counting numbers, there exists an additional way to imagine convergence. Both methods are described below.

Definition Let (xn) be a sequence of real numbers. The sequence (xn) is said to converge to a real number a.
if for all ε>0, there exists N in N such that |xn-a|<ε for all nN.

If (xn) converges to a then we say a is the limit of (xn) and write

or

as .

This is read xn approaches a as n approaches ∞. If it is clear which variable is playing the role of n then this may be abbreviated to simply xna or lim xn=a.

If a sequence converges, then it is called convergent.

It is also useful to extend this concept and allow sequences whose limits are either ∞ or −∞

Definition We say xn→∞ as n→∞ if for every M in R there is a natural number N so that xn≥ M for all nN. We say xn→−∞ as n→∞ if for every M in R there is a natural number N so that xn≤ M for all nN.

Despite this, we do not refer to sequences such as these as convergent. They are instead called divergent.

Although convergence can be proven using the epsilon-delta definition as proof, another method to prove convergences of sequences is through mathematical induction, since sequences are referenced using counting numbers. Through this method, some theorems are easier to prove. However, proof using mathematical induction cannot generalize to real numbers like a proof using epsilon-delta can.

The following theorems will prove that variations of a convergent sequence, expressed either through inductive notation, limit notation, or Cauchy notation, converges to exactly one number. This may seem intuitively clear, but remember that intuition often fails us when it comes to limits. It is also in proper mathematical style to rigorously prove every mathematical notion presented to us.

Theorem (Uniqueness of limits)

A sequence can have at most one limit. In other words: if xn → a and xn → b then a = b.

Proof

Suppose the sequence has two distinct limits, so ab. Let ε=|ab|/3.

Certainly ε>0, using the definition of convergence twice we can find natural numbers Na and Nb so that

for all n > Na.

and

for all n > Nb.

Taking k=max(Na,Nb) then both of these conditions hold for xk. Hence we deduce that |xka|≤ε and |xkb|≤ε. Applying the triangle inequality, we see

which is a contradiction. Thus, any sequence has at most one limit.

Theorem (Convergent Sequences Bounded)

If the subsequence is a convergent sequence, then it is bounded.

Proof

Let , and let ε = 1.

From the definition of convergence there exists a natural number N such that

for all n ≥ N.

The sequence is bounded above by a+1 and below by a−1. Let M = max(|x1|,|x2|,|x3|,…,|xN|, |a|+1). It follows that −M ≤ xn ≤ M for all n in N. Hence the sequence is bounded.

Theorem (Boundedness of Cauchy Sequences)

If is a Cauchy sequence, then it is bounded.

Proof

Let (xn) be a Cauchy sequence. By the definition of a Cauchy sequence, there is a natural number N such that |xnxm|<1 for all n,m > N. In particular, |xN+1xm|<1 for all m > N. It follows by the reverse triangle inequality that |xm| < |xN+1| + 1. If we take M=max(|x1|, |x2|, …, |xN|, |xN+1| + 1), then |xn| ≤ M for all n in N.

The following theorem tells us that algebraic operations on sequences commute with the taking limits. This simple theorem is a useful tool in computing limits.

Properties of Sequences

Given our new definition of convergence, it should be essential that we can use the values we get from them algebraically and whether or not we can apply algebraic intuition in regards to converging sequences as well.

Algebraic Operations

If (xn) and (yn) are convergent sequences and a ∈ R, the following properties hold:

  1. .
  2. .
  3. .
  4. (assuming yn ≠ 0 for all n in N and lim y_n ≠ 0).
  5. If xn ≤ yn for every n in N, then .

Proof

1. Let x=lim xn and y=lim yn. We need to show that for any ε>0 there is natural number N so that if nN, then |(xn + yn) − (x + y)|≤ε. Given any ε>0 we have ε/3>0 so from the definition of convergence there is a natural number Nx so that |xnx|≤ε/3 for all n>Nx, similarly we can choose Ny |yny|≤ε/3 for all n>Ny.

Let N=max(Nx ,Ny). If n>N, then by the triangle inequality we have

which is what we needed to show.

2. Let x=lim xn and y=lim yn. Since these sequences are convergent they are bounded. Let Mx be a bound for (xn) and let My be a bound for (yn). By increasing these quantities of necessary we may also assume Mx > x and My > y. Given ε>0, there exists some Nx and Ny such that

for n > Nx and
for n > Ny.

Then for every n > max(NxNy),

3. Let yn = a for all n in N. The statement now follows from 2.

4. We can reduce this to showing that lim (1/yn) exists and equals 1/(lim yn). Then it follows by 2 that we have:

Let y=lim yn. By the exercises, since y and yn are not 0, we can find δ > 0 so that |y_n| > δ and |y| > δ. It follows that 1/|yny|<1/δ2. Given ε > 0 choose n in N so that |yn − y| < δ2ε. We have

.

Hence,

5. We first can reduce to the case when one sequence is identically 0. To see this let zn = xn − yn. Then zn < 0 for all n in N. Let z = lim zn. Suppose that z > 0 then we can then find a natural number N so that

.

Since zN ≤ 0 < z, the absolute value equals z − zN. Subtracting z we find that −zN < 0. Hence zN is positive. Contradiction. Therefore we must have that z ≤ 0. Which means that by 1 we get:

Therefore lim xn ≤ lim yn

Theorem (Squeeze/Sandwich Limit Theorem)

This is the important squeeze theorem that is a cornerstone of limits. SInce converging sequences can also be thought of through limit notions and notations, it should also be wise if this important theorem applies to converging sequences as well.

Given sequences (xn), (yn), and (wn), if (xn) and (yn) converge to a and xn ≤ wn ≤ yn, then wn converges to a.

Proof

Fix ε > 0. We need to find an N such that |wn − a| < ε if n > N. Since (xn) → a and (yn) → a the definition of convergence ensures that there exists integers Nx and Ny so that |xn − a| < ε for n > Nx and |yn − a| < ε for n > Ny.

Let N=max(NxNy). Then, for all n > N we have −ε < xn − a and yn − a < ε. Since xn < wn < yn, it follows that xn − a < wn − a < yn − a.

Thus if n ≥ N, then −ε < xn − a < wn − a < yn − a < ε. In other words, |wn − a| < ε.

Completeness

The following results are closely related to the completeness of the real numbers.

Theorem (Convergence of Monotone sequences)

Any monotone, bounded sequence converges. If the sequence is non-decreasing, then the sequence converges to the least upper bound of the elements of the sequence. If the sequence is non-increasing, then the sequence converges to the greatest lower bound of the elements of the sequence

Proof

Let (xn) be any monotone sequence that is bounded by a real number M. Without loss of generality, assume (xn) is non-decreasing. Since (xn) is bounded above, it has a least upper bound by the least upper bound axiom. Let x = sup {xn | n ∈ N}. We will now show that (xn) → x.

Fix ε > 0. As was shown in the exercises, if s = sup(A), then for any ε > 0 there is an element a in A so that s − ε < a < s. Hence, it follows that there exists an N in N so that x − ε < xN < x.

For any n > N, since xn is non-decreasing, we have that

.

Thus |x − xn| < ε and by the definition of convergence, (xn) converges to x.

Theorem (Nested intervals property)

If there exists a sequence of closed intervals In = [anbn] = {x | an ≤ x ≤ bn} such that In+1 ⊆ In for all n, then ∩In is nonempty.

Proof

Since In+1 ⊆ In it follows that an ≤ an+1 and bn+1 ≤ bn.

Since (an) and (bn) are monotonic sequences they converge by the previous theorem. Furthermore, since an < bn for all n, it follows that lim an ≤ lim bn .

By the monotonicity of (an) and (bn) we have for every n

Therefore lim an ∈ [anbn] for every n, which implies that

Thus the intersection is nonempty.

Theorem (Bolzano—Weierstrass)

Every bounded sequence of real numbers contains a convergent subsequence.

Proof

Let (xn) be a sequence of real numbers bounded by a real number M, that is |xn| < M for all n. We define the set A by A = {r | |r| ≤ M and r < xn for infinitely many n}. We note that A is non-empty since it contains −M and A is bounded above by M. Let x = sup A.

We claim that, for any ε > 0, there must be infinitely many points of xn in the interval (x − ε, x + ε). Suppose not and fix an ε > 0 so that there are only finitely many values of xn in the interval (x − ε, x + ε). Either x ≤ xn for infinitely many n or x ≤ xn for at most only finitely many n (possibly no n at all). Suppose xxn for infinitely many n. Clearly in this case x ≠ M. If necessary restrict ε so that x + ε ≤ M. Set r = x + ε/2 we have that r < xn for infinitely many n because there are only finitely many xn in the set [x,r] and x must be less than infinitely many xn, furthermore |r| < M. Thus r is in A, which contradicts that x is an upper bound for A. Now suppose xxn for at most finitely many n. Set y = x − ε/2. Then there are at most only finitely man n so that xn ≥ y. Thus, if r < xn for infinitely many n, we have that r ≤ y. This means that y is an upper bound for A that is less than x, contradicting that x wast the least upper bound of A. In either case we arrive at a contradiction, thus we must have that for any ε > 0, there must be infinitely many points of xn in the interval (x − ε, x + ε).

Now we show there is a subsequence that converges to x. We define the subsequence inductively, choose any xn1 from the interval (x − 1, x + 1). Assuming we have chosen xn1, …, xnk−1, choose xnk to be an element in the interval (x − 1/k, x + 1/k) so that nk∉{n1, …, nk−1}, this is possible as there are infinitely many elements of (xn) in the interval. Notice that for this choice of xnk we have that |x − xnk|<1/k. Hence for any ε>0, if we take any k > 1/ε, then |xnk-x| < ε. That is the subsequence (xnk) → x.

Theorem (Cauchy criterion)

A sequence converges if and only if it is Cauchy. Although this seems like a weaker property than convergence, it is actually equivalent, as the following theorem shows:

Proof

First we show that if (xn) → x then xN is Cauchy. Now suppose that for a given ε > 0 we wish to find an N so that |xn − xm| < ε for all nm > N. We will choose N so that for all n ≥ N we have that |xn − x| < ε/2. By the triangle inequality, for any nm > N we have:

.

Thus (xn) is a Cauchy sequence.


Now we show that if (xn) is a Cauchy sequence, then it converges to some x. Let (xn) be a Cauchy sequence, and let ε > 0. By the definition of a Cauchy Sequence, there exits a natural number L so that |xn − xm| < ε/2 whenever nm > L. Since (xn) is a Cauchy sequence it is bounded. By the Bolzano—Weierstrass theorem, it has a convergent subsequence (xnk) that converges to some point x. Now we will show that the whole sequence converges to x

Because (xnk) converges, we can choose a natural number M so that if nk > M, then |xnk − x| < ε/2. Let N = max(LM), and fix any nk > N. For n > N we have that

.

Thus by definition of convergence (xn) → x.


These theorems all describe different aspects of the completeness of the real numbers. The reader will notice that the least upper bound property was used heavily in this section, and it is the axiom that separates the real numbers from the rational numbers. While these theorems would be false for the rational numbers, not all of them can substitute for the least upper bound property. The Cauchy criterion and the nested intervals property are not strong enough to imply the least upper bound property without additional assumptions, while the Convergence of Monotone sequences theorem and the Bolzano—Weierstrass property do imply the least upper bound property.

Contractive Sequence (Definition)

A sequence of real numbers is contractive if there exists some constant , , such that

for all .

Every contractive sequence is also a Cauchy sequence (this proof is left to the reader as an exercise), and thus every contractive sequence is convergent by the Cauchy Criterion. However, note that this does not mean that every Cauchy sequence is contractive. The reader is encouraged to find a counterexample to prove this statement (that is, find a sequence that is convergent, and thus Cauchy, that is NOT contractive).

Limit superior and limit inferior

Limits turn out to be a very useful tool in analysis, their primary draw back is that they may not always exist. Occasionally it is useful to have some notion of limit that makes sense for any sequence. To this end we introduce the limit superior (often just called the "lim sup") and the limit inferor (often called the "lim inf").

Definition For a sequence (xn) we define the limit superior, denoted lim sup by:

Similarly we define the limit inferior, deonoted by lim inf by:

If (xn) is not bounded above, we say that lim sup xn = ∞. If (xn) is not bounded we say that lim inf xn = −∞.

Notice that for bounded sequences the lim sup and the lim inf always exist. As we know general bounded sequence the limit doesn't always exist. But in the case when the lim sup and lim inf are equal, life is nicer as the next theorem shows.

Theorem (Limit Superior and Inferior)

Let (xn) be a bounded sequence. Then (xn) → x if and only if lim sup xn = x = lim inf xn.

Proof

First suppose (xn) → x. Fix an ε > 0 choose a natural number N so that x − ε < xn < x + ε for any n > N. Hence for any k > N we have that

and hence x − ε < lim sup xn < x + ε. Since ε was arbitrary, this can only happen if lim sup xn = x. A similar argument shows that lim inf xn = x.

Now suppose lim inf xn = x = lim sup xn, and we wish to show that lim xn = x.

First recall that the x=lim sup xn is defined as:

Given an ε > 0, since we can get arbitrarily close to the infimum, we can choose we will choose Nls so that

Similarly recall that the x=lim inf xn is defined as:

Since we can get arbitrarily close to the supremum, we can choose we will choose Nli so that

Let N = max(NlsNli). Now if n > N, then

Hence for any n > N

By our choice of Nls and Nli this implies for any n > N

The Tail of a Sequence of Real Numbers

We will now look at an important aspect of a sequence known as the tail of a sequence.

Definition: Let be a sequence of real numbers. Then for any , the -Tail of is a the subsequence .

Recall that for a sequence that converges to the real number then , that is there exists a natural number such that if then . For any given positive we can consider the -tail of the sequence to be the subsequence of such that all terms in this tail are within an -distance from our limit . The diagram below illustrates this concept.

The following theorem tells us that the m-tail of a sequence must also converge to the limit provided the parent sequence converges to .

Theorem 1: Let be a sequence of real numbers. Then converges to if and only if for any the -tail of , call it converges to .

Subsequence

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence is a subsequence of obtained after removal of elements and The relation of one sequence being the subsequence of another is a preorder.

Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as from is a substring. The substring is a refinement of the subsequence.

The list of all subsequences for the word "apple" would be "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "e", "" (empty string).

Common subsequence

Given two sequences and a sequence is said to be a common subsequence of and if is a subsequence of both and For example, if

then is said to be a common subsequence of and

This would not be the longest common subsequence, since only has length 3, and the common subsequence has length 4. The longest common subsequence of and is

Applications

Subsequences have applications to computer science, especially in the discipline of bioinformatics, where computers are used to compare, analyze, and store DNA, RNA, and protein sequences.

Take two sequences of DNA containing 37 elements, say:

SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

The longest common subsequence of sequences 1 and 2 is:

LCS(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

This can be illustrated by highlighting the 27 elements of the longest common subsequence into the initial sequences:

SEQ1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
SEQ2 = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Another way to show this is to align the two sequences, that is, to position elements of the longest common subsequence in a same column (indicated by the vertical bar) and to introduce a special character (here, a dash) for padding of arisen empty subsequences:

SEQ1 = ACGGTGTCGTGCTAT-G--C-TGATGCTGA--CT-T-ATATG-CTA-
        | || ||| ||||| |  | |  | || |  || | || |  |||
SEQ2 = -C-GT-TCG-GCTATCGTACGT--T-CT-ATTCTATGAT-T-TCTAA

Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine.

Theorems

  • Every infinite sequence of real numbers has an infinite monotone subsequence (This is a lemma used in the proof of the Bolzano–Weierstrass theorem).
  • Every infinite bounded sequence in has a convergent subsequence (This is the Bolzano–Weierstrass theorem).
  • For all integers and every finite sequence of length at least contains a monotonically increasing subsequence of length  or a monotonically decreasing subsequence of length  (This is the Erdős–Szekeres theorem).

Licensing

Content obtained and/or adapted from: