Real analysis/Sequences

Definition

A sequence of real numbers is any function $a:\mathbb{N}\to ℝ$. However, we usually write $a_n$ for the image of $n$ under $a$, rather than $a(n)$. The values $a_n$ are called the elements of the sequence.

The sequence as a whole may be written $(a_n{)}_{n=1}^{\mathrm{\infty }}$ (or just $(a_n)$). When specifying a particular sequence, it may be written in the form $(a_1,a_2,a_3,\dots )$, where sufficiently many elements of the sequence are given so that the pattern is clear.

For example, $(1,2,3,4,\dots )$, $(1,-2,3,-4,\dots )$, and $(1,\pi ,{\pi }^2,{\pi }^3,{\pi }^4,\dots )$ are all sequences. Note, however, that there need not be any particular pattern to the elements of the sequence, but it is of course difficult to give an example of a sequence without a pattern.

In a general context sequences such as these would be referred to as real sequences, sequences of real numbers or sequences in $ℝ$ to make it clear that the elements of the sequence are elements of $ℝ$. However, since we are concerned primarily with the real numbers, it may be assumed that all sequences are real sequences unless otherwise stated.

Classification of Sequences

Some properties of sequence are so important that they are given special names. A sequence $(a_n{)}_{n=1}^{\mathrm{\infty }}$ is called

1. strictly increasing if $\mathrm{\forall }n\in \mathbb{N}:a_n<a_{n+1}$.
2. non-decreasing if $\mathrm{\forall }n\in \mathbb{N}:a_n\le a_{n+1}$.
3. strictly decreasing if $\mathrm{\forall }n\in \mathbb{N}:a_n>a_{n+1}$.
4. non-increasing if $\mathrm{\forall }n\in \mathbb{N}:a_n\ge a_{n+1}$.
5. monotone if it satisfies any of the above properties (i.e. if it is either non-decreasing or non-increasing).
6. strictly monotone if it is either strictly increasing or strictly decreasing.
7. bounded above if there exists $M\in ℝ$ such that $\mathrm{\forall }n\in \mathbb{N}:a_n<M$.
8. bounded below if there exists $M\in ℝ$ such that $\mathrm{\forall }n\in \mathbb{N}:a_n>M$.
9. bounded if it is both bounded above and bounded below.
10. Cauchy if $\mathrm{\forall }ϵ>0\mathrm{\exists }N:\mathrm{\forall }n,m>N,|a_m-a_n|<ϵ$

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 terms are ambiguous and we try to avoid their use here.

Convergence

A further important property of sequences (arguably the most important property from the perspective of analysis) is the property of convergence.

Let $(x_n{)}_{n=1}^{\mathrm{\infty }}$ be a sequence and let $a\in ℝ$. The sequence is said to converge to $a$ if, for all $ϵ>0$, there exists $N\in \mathbb{N}$ such that $n\ge N$ implies $|x_n-a|\le ϵ$. We write this more concisely as

$\mathrm{\forall }ϵ>0:\mathrm{\exists }N:\mathrm{\forall }n\ge N:|x_n-a|\le ϵ$.

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

$a=\underset{n\to \mathrm{\infty }}{\lim }{x}_n$

or

$x_n\to a$ as $n\to \mathrm{\infty }$

This is read $x_n$ tends to $a$ as $n$ tends to $\mathrm{\infty }$. If it is clear which variable is playing the role of $n$ then this may be abbreviated to simply $x_n\to a$.

If a sequence has a limit, then it is called convergent.

It is also useful to extend this concept and allow sequences whose limits are either $\mathrm{\infty }$ or $-\mathrm{\infty }$. We say $x_n\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$ if

$\mathrm{\forall }M\in ℝ:\mathrm{\exists }N:\mathrm{\forall }n\ge N:x_n\ge M$.

and $x_n\to -\mathrm{\infty }$ as $n\to \mathrm{\infty }$ if

$\mathrm{\forall }M\in ℝ:\mathrm{\exists }N:\mathrm{\forall }n\ge N:x_n\le M$.

Despite this, we do not refer to sequences such as these as convergent. Indeed, such sequences are unbounded (Exercise: prove this), and so the theorem below that convergent sequences are bounded shows that such sequences cannot possibly be convergent.

Theorem (Uniqueness of limits)

A sequence can have at most one limit. In other words: if $x_n\to a$ and $x_n\to b$ then $a=b$.

Proof

Suppose the sequence has two distinct limits, so $a=b$. Let $ϵ=|a-b|/3$.

Certainly $ϵ>0$, so we can apply the defining property of the sequence (twice) to obtain

$N_a:\mathrm{\forall }n\ge N_a:|x_n-a|\le ϵ$

and also

$N_b:\mathrm{\forall }n\ge N_b:|x_n-b|\le ϵ$

So, in particular, if we take $n=\max (N_a,N_b)$ then both of these conditions hold for $n$, and so we deduce that $|x_n-a|\le ϵ$ and also $|x_n-b|\le ϵ$. Applying the triangle inequality for $ℝ$, we deduce that $|a-b|\le 2ϵ=(2/3)|a-b|$, which is a contradiction.

Thus, we deduce that our original assumption (that the sequence had two distinct limits) was false, and so any sequence can have at most one limit. $◻$

Theorem (Convergent Sequences Bounded)

If $(x_n{)}_{n=1}^{\mathrm{\infty }}$ is a convergent sequence, then it is bounded.

Proof

Let $a=\underset{n\to \mathrm{\infty }}{\lim }{x}_n$, and let $ϵ=1$.

From the definition of convergence there exists a corresponding $N$ such that

$\mathrm{\forall }n\ge N:|x_n-a|\le 1$

The sequence $(x_n{)}_{n=N+1}^{\mathrm{\infty }}$ is bounded above by $a+1$ and below by $a-1$. Now consider the finite sequence $(x_1,x_2,\dots ,x_N)$. Let $M=\max (|x_1|,|x_2|,|x_3|,\dots ,|x_N|,|a|+1)$. It follows that $\mathrm{\forall }n:-M\le x_n\le M$ and the sequence is thus bounded. $◻$

Theorem (Boundedness of Cauchy Sequences)

Let $(x_n{)}_{n=1}^{\mathrm{\infty }}$ be a Cauchy sequence. There is an N such that when a>N and b>N, that d(x_a,x_b)<ε. Consider a_N+1. Then when b>N, d(x_N+1,x_b)<ε. Then consider the maximum of the finite set r=max{x|x=d(x_N+1,x_a for some a≤N or x=ε). Then the ball B_r(x_N+1) contains all the elements of the set, and hence it is bounded.

Subsequences

Given a sequence $(x_n{)}_{n=1}^{\mathrm{\infty }}$, a subsequence of this sequence is a sequence $(x_{n_j}{)}_{j=1}^{\mathrm{\infty }}$, where $(n_j{)}_{j=1}^{\mathrm{\infty }}$ is itself a strictly increasing sequence of natural numbers.

For example, taking $n_j=2j$ would provide a subsequence consisting of every other element of the original sequence, that is $(x_2,x_4,x_6,\dots )$.

Theorem (Subsequence Convergence)

If $(x_n{)}_{n=1}^{\mathrm{\infty }}$ converges to $a\in ℝ$, every subsequence $(x_{n_j}{)}_{j=1}^{\mathrm{\infty }}$ converges to $a$.

Proof

Let $ϵ>0$.

From the definition of convergence, there exists a $N\in \mathbb{N}$ such that $n\ge N$ implies $|x_n-a|\le ϵ$.

Since $n_k$ is a strictly increasing sequence of natural numbers, $n_j\ge j$ (Exercise: prove this fact. There is a simple proof by induction).

It follows that $j\ge N$ implies $|x_{n_j}-a|\le ϵ$. This is the required property. $◻$

Algebraic Operations on Sequences

We can also perform algebraic operations on sequences. In other words, we can add, negate, subtract, multiply, invert and divide sequences. This is useful because, when the sequences converge, taking the limits commutes with the algebraic operation --- in other words, the limit of a sum of two sequences is equal to the sum of the individual limits, and similarly for the other operations. The following theorem makes this explicit.

Theorem (Algebraic Operations)

If $(x_n)$ and $(y_n)$ are convergent sequences and $a\in ℝ$, the following properties hold:

• (i) $\underset{n\to \mathrm{\infty }}{\lim }(x_n+y_n)=\underset{n\to \mathrm{\infty }}{\lim }(x_n)+\underset{n\to \mathrm{\infty }}{\lim }(y_n)$.
• (ii) $\underset{n\to \mathrm{\infty }}{\lim }(x_n{y}_n)=\left(\underset{n\to \mathrm{\infty }}{\lim }{x}_n\right)\left(\underset{n\to \mathrm{\infty }}{\lim }{y}_n\right)$.
• (iii) $\underset{n\to \mathrm{\infty }}{\lim }(a{x}_n)=a\underset{n\to \mathrm{\infty }}{\lim }(x_n)$.
• (iv) If $\mathrm{\forall }n:y_n\ne 0$, then $\underset{n\to \mathrm{\infty }}{\lim }\left(\frac{x_n}{y_n}\right)=\frac{\underset{n\to \mathrm{\infty }}{\lim }{x}_n}{\underset{n\to \mathrm{\infty }}{\lim }{y}_n}$ (assuming $\underset{n\to \mathrm{\infty }}{\lim }{y}_n\ne 0$).
• (v) If $\mathrm{\forall }n:x_n\le y_n$, then $\underset{n\to \mathrm{\infty }}{\lim }{x}_n\le \underset{n\to \mathrm{\infty }}{\lim }{y}_n$.

Proof

• (i) Let $a=\underset{n\to \mathrm{\infty }}{\lim }{x}_n$ and $b=\underset{n\to \mathrm{\infty }}{\lim }{y}_n$. We need to show that $\mathrm{\forall }ϵ>0:\mathrm{\exists }N:\mathrm{\forall }n\ge N:|(x_n+y_n)-(a+b)|\le ϵ$.

Given any $ϵ>0$ we have $ϵ/3>0$ so from the definition of convergence $\mathrm{\exists }{N}_x:\mathrm{\forall }n\ge N_x:|x_n-a|\le ϵ/3$ and $\mathrm{\exists }{N}_y:\mathrm{\forall }n\ge N_y:|y_n-b|\le ϵ/3$.

Letting $N=\max (N_x,N_y)$, we have from the triangle inequality for $ℝ$,

$\mathrm{\forall }n\ge N:|(x_n-a)+(y_n-b)|\le ϵ/3+ϵ/3$ or $\mathrm{\forall }n\ge N:|(x_n+y_n)-(a+b)|\le 2ϵ/3<ϵ$ which is what we had to prove.

(ii) Let $ϵ>0$ be given. By hypothesis there exists some $N_1$ and $N_2$ such that

$|x_n-x|<\frac{ϵ}{2}\frac{1}{1+|y|}$ for $n>N_1$and $|y_n-y|<\min \{1,\frac{1}{|x|}\frac{ϵ}{2}\}$ for $n>N_2$.

Then we have: for all $n$ such that $n>N_1$ and $n>N_2$:

$|x_n{y}_n-xy|$	$=|(x_n-x)(y_n-y)+x(y_n-y)+(x_n-x)y|$
	$\le |(x_n-x)(y_n-y)|+|x||y_n-y|+|x_n-x||y|$
	$\le |(x_n-x)|(1+|y|)+|x||y_n-y|$ (since $|y_n-y|<1$)
	$<\frac{ϵ}{2}\frac{1}{1+|y|}(1+|y|)+|x|\frac{1}{|x|}\frac{ϵ}{2}$
	$=\frac{ϵ}{2}+\frac{ϵ}{2}$
	$=ϵ.$

(iii) Let $y_n$ = the sequence: $a,a,a,...$. Then the statement follows from (ii).

TODO

Theorem (Squeeze/Sandwich Limit Theorem)

Given sequences $(x_n)$, $(y_n)$, and $(w_n)$, if $x_n$ and $y_n$ converge to $a$ and $x_n\le w_n\le y_n$, $w_n$ converges to $a$.

Proof

Let $ϵ>0$.

We need to find an $N$ such that $\mathrm{\forall }n\ge N,|w_n-a|<ϵ$.

Since $(x_n)\to a$ and $(y_n)\to a$, so from the definition of convergence

$\mathrm{\exists }{N}_1,N_2:\mathrm{\forall }n\ge N_1,|x_n-a|<ϵ$ and $\mathrm{\forall }n\ge N_2,|y_n-a|<ϵ$.

Let $N=\max \{N_1,N_2\}$. Then $\mathrm{\forall }n\ge N,-ϵ<x_n-a$ and $y_n-a<ϵ$

Since $x_n\le w_n\le y_n$, we have $x_n-a\le w_n-a\le y_n-a$.

Thus $\mathrm{\forall }n\ge N,$ $-ϵ<x_n-a\le w_n-a\le y_n-a<ϵ$.

In other words, $|w_n-a|<ϵ$, which is what we wanted.$◻$

Other Completeness Axioms

As promised earlier, here are several equivalent formulations of the completeness axiom.

Theorem (Monotone Convergence)

Any monotone, bounded sequence converges.

Proof

Let $(x_n)$ be any monotone sequence that is bounded by a real number M. Without loss of generality, let $(x_n)$ be increasing.

First, we must use the completeness axiom. Since $(x_n)$ is bounded above, it has a least upper bound.

Let $x=sup\{x_n\}$. Now we must show that$(x_n)\to x$.

It follows from the definition of supremum(Prove it) that if s = sup($A$) then $\mathrm{\forall }ϵ>0:\mathrm{\exists }a\in A:s-ϵ<a<s$.

Applying this to the current situation, we see that $\mathrm{\exists }N:x-ϵ<x_N<x$.

Since $(x_n)$ is increasing, $x-ϵ<x_N\le x_n<x$ $\mathrm{\forall }n\ge N$.

Thus $\mathrm{\forall }n\ge N,|x-x_n|<ϵ$. By the definition of convergence, $(x_n)$ converges to $x$. $◻$

Theorem (Nested Interval Property)

If there exists a sequence of closed intervals $I_n=[a_n,b_n]=\{x:a_n\le x\le b_n\}$ such that $I_{n+1}\subset I_n$ for all n, then $\underset{n=1}{\overset{\mathrm{\infty }}{\cap }}{I}_n$ is nonempty.

Proof

Note that this is obvious if you know some basic topology. However, that isn't necessary.

Since $I_{n+1}\subset I_n$ $a_{n+1},b_{n+1}\in I_n$. So, $a_n\le a_{n+1}$ and $b_n\ge b_{n+1}$.

Thus $(a_n)$ and $(b_n)$ are monotone sequences, which must converge by the previous theorem.

Since $a_n<b_n\mathrm{\forall }n$, $\underset{n\to \mathrm{\infty }}{\lim }{a}_n\le \underset{n\to \mathrm{\infty }}{\lim }{b}_n$.

Furthermore, $\underset{n\to \mathrm{\infty }}{\lim }{a}_n=\sup \{a_n\}$ and $\underset{n\to \mathrm{\infty }}{\lim }{b}_n=\inf \{b_n\}$, by the previous proof.

Thus $a_n\le \underset{n\to \mathrm{\infty }}{\lim }{a}_n\le \underset{n\to \mathrm{\infty }}{\lim }{b}_n\le b_n$, so$\underset{n\to \mathrm{\infty }}{\lim }{a}_n\in [a_n,b_n]$.

Since this holds for all n, $\underset{n\to \mathrm{\infty }}{\lim }{a}_n\in \underset{n=1}{\overset{\mathrm{\infty }}{\cap }}{I}_n$, showing that the intersection is indeed nonempty.$◻$

Theorem (Bolzano-Weierstrass)

Every bounded sequence of real numbers contains a convergent subsequence.

Proof

Let $(x_n)$ be any sequence bounded by M. The idea is to confine a subsequence to successively smaller intervals whose length approaches 0. Construct a sequence of nested intervals $I_n=[a_n,b_n]$ and a subsequence $x_{n_k}$ inductively (make sure you know what this means) as follows:

1) Let $a_0=-M,b_0=M$. Since $(x_n)$ is bounded by M, infinitely many terms of $(x_n)$ lie in $I_0$. Pick one of these and call it $x_{n_0}$.

2) Given $I_k=[a_k,b_k]$, consider the intervals $J=[a_k,\frac{a_k+b_k}{2}],K=[\frac{a_k+b_k}{2},b_k]$. By induction, infinitely many terms of $(x_n)$ lie in $I_k$. Thus one of the intervals J, K must contain infinitely many terms of $(x_n)$. Call this interval $I_{k+1}$. Pick one of the terms of $(x_n)$ that lie in $I_{k+1}$, and call it $x_{n_{k+1}}$

By the Nested Interval Property, $\underset{n=1}{\overset{\mathrm{\infty }}{\cap }}{I}_n$ is non-empty. Say it contains the number $x$. This number is unique, but we don't need to prove it. We only have to show that $(x_{n_k})$ converges to x.

By the construction of the intervals $I_k$, $|a_k-b_k|=\frac{M}{2^k}$. Since both $x_{n_k},x\in I_k$, $|x-x_{n_k}|<|a_n-b_n|<\frac{1}{2^k}$. (This step is not completely rigorous, but an ugly triangle inequality argument can be made to justify it)

Thus $\mathrm{\forall }ϵ:\mathrm{\exists }k:|x-x_{n_k}|<\frac{1}{2^k}<ϵ$. By definition, $(x_{n_k})\to x$, which is what we wanted.$◻$

Theorem (Cauchy Criterion)

A sequence converges if and only if it is Cauchy. If you read about the construction of the real numbers, you may already be familiar with Cauchy sequences. If not, we repeat the definition here:

A sequence $(x_n)$ is Cauchy if $\mathrm{\forall }ϵ:\mathrm{\exists }N:\mathrm{\forall }n,m\ge N:|x_n-x_m|<ϵ$ Although this seems like a weaker property than convergence, it is actually equivalent, as the following theorem shows:

Proof

($\to$) Let $(x_n)\to x$.

Then $\mathrm{\forall }ϵ>0,\mathrm{\exists }N:\mathrm{\forall }n\ge N:|x_n-x|<\frac{ϵ}{2}$. Applying the triangle inequality, we see that

$\mathrm{\forall }n,m\ge N:|x_n-x_m|\le |x_n-x|+|x_m-x|<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$.

Thus $(x_n)$ is Cauchy.

($\leftarrow$) Let $(x_n)$ be Cauchy, and let $ϵ>0$.

By definition of a Cauchy Sequence, $\mathrm{\exists }N:\mathrm{\forall }n,m\ge N:|x_n-x_m|<\frac{ϵ}{2}$. Now consider the subsequence $(x_n{)}_{n=N}^{\mathrm{\infty }}$. If $x_n\in (x_n{)}_{n=N}^{\mathrm{\infty }}$, then $|x_n|\le |x_n-x_N|+|x_N|\le \frac{ϵ}{2}+|x_N|$.

Thus $(x_n{)}_{n=N}^{\mathrm{\infty }}$ is bounded. By the Bolzano-Weierstrass Theorem, it has a convergent subsequence, $(x_{n_k})\to x$.

Since $(x_{n_k})\to x$, $\mathrm{\exists }M>N:\mathrm{\forall }{n}_k\ge M:|x_{n_k}-x|<\frac{ϵ}{2}$. Thus $\mathrm{\forall }n\ge M:|x_n-x|\le |x_n-x_{n_k}|+|x_{n_k}-x|<\frac{ϵ}{2}+\frac{ϵ}{2}=ϵ$. Thus by definition of convergence $(x_n)\to x$.$◻$

Types of Convergence

There are many different types of convergence, of which three are listed here(there may be more in the future). The first, as we have already seen, is logically equivalent to the original definition of convergence, whereas the other two are (logically) weaker.

• Cauchy convergence: See above.

• Cesaro Mean convergence: We say a sequence $(x_n)$ converges to $x$ by Cesaro means if the sequence of averages $(\frac{x_1+x_2+...+x_n}{n})$ converges to $x$.

• Limit Superior: We define $\underset{n\to \mathrm{\infty }}{\lim }\sup (x_n)$ for any bounded sequence $(x_n)$ by the following: Let $y_n=\sup \{x_k:k\ge n\}$. Then $\underset{n\to \mathrm{\infty }}{\lim }\sup (x_n)=\underset{n\to \mathrm{\infty }}{\lim }(y_n)$. The limit inferior is defined similarly, replacing "sup" with "inf".

As a self-test, the reader might try to prove the following theorems on their own before continuing.

Theorem (Cesaro Mean Convergence)

If $(x_n)\to x$, then $(x_n)\to x$ by Cesaro means.

Proof

there is no proof you have to do

Theorem (Limit Superior and Inferior)

$\underset{n\to \mathrm{\infty }}{\lim }\sup (x_n)$ exists for any bounded sequence $(x_n)$. Furthermore, whenever $\underset{n\to \mathrm{\infty }}{\lim }(x_n)$ exists, $\underset{n\to \mathrm{\infty }}{\lim }\sup (x_n)=\underset{n\to \mathrm{\infty }}{\lim }(x_n)$

Proof

TODO

Recursively Defined Sequences

We can define a sequence recursively by specifying an initial value and a recursion relation:

$x_0=a$

$x_n=f(x_{n-1})$

In this case, it isn't hard to see that $\underset{n\to \mathrm{\infty }}{\lim }{x}_n=\underset{n\to \mathrm{\infty }}{\lim }f(x_n)$ (As an exercise, prove this rigorously). Recursive sequences are very useful for this reason; the limit only depends on the recursion relation. Thus, in order to find a sequence with a certain limit, we only have to find an algebraic expression satisfied by the limit and specify an initial condition that ensures convergence of the sequence. For example, if we want a sequence that converges to the golden ratio $\varphi =(1+\sqrt{5})/2$, we notice that $\varphi$ is a root of the polynomial x^2 - x - 1 = 0, and define the sequence as follows:

$x_0=1$

$x_n=1+\frac{1}{x_{n-1}}$

If L is the limit of this sequence, then $L=1+\frac{1}{L}⟹L^2=L+1⟹L^2-L-1=0$. Thus the limit must be a root of this quadratic. Since it is clear that this sequence must always be positive, the only possible limit is $\varphi$. A bit more work shows that the sequence is bounded and contains two monotone subsequences, $x_{2n}$ and $x_{2n+1}$, each of which converge by the monotone convergence theorem, and whose difference converges to 0 (exercise:prove this). Thus both subsequences have the same limit, the limit of the sequence, which must be $\varphi$. In fact, this sequence convergences very, very rapidly, faster than $\frac{1}{q_n^2}$, where $q_n$ is the denominator of the rational number $x_n$. It is somewhat amazing that we can prove such things given little more than a recursion formula.

The type of recursive sequence used above is called a "continued fraction" (write out each term $x_n$ explicitly to see why). These sequences are very important in the subject of Number Theory. A class examples that are perhaps more important to Analysis are the sequences defined by Newton's method for approximating zeros of differentiable functions:

$x_n=x_{n-1}+\frac{f(x_{n-1})}{f^{\prime }(x_{n-1})}$

We will discuss these later, after we define the derivative.