Convergence proof techniques

Convergence proof techniques are canonical components of mathematical proofs that sequences or functions converge to a finite limit when the argument tends to infinity.

There are many types of series and modes of convergence requiring different techniques. Below are some of the more common examples. This article is intended as an introduction aimed to help practitioners explore appropriate techniques. The links below give details of necessary conditions and generalizations to more abstract settings. The convergence of series is already covered in the article on convergence tests.

Convergence in Rⁿ

It is common to want to prove convergence of a sequence ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {R} ^{n}}$ or function ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} ^{n}}$, where ${\displaystyle \mathbb {N} }$ and ${\displaystyle \mathbb {R} }$ refer to the natural numbers and the real numbers, and convergence is with respect to the Euclidean norm, ${\displaystyle ||\cdot ||_{2}}$.

Useful approaches for this are as follows.

First principles

The analytic definition of convergence of ${\displaystyle f}$ to a limit ${\displaystyle f_{\infty }}$ is that ^[1] for all ${\displaystyle \epsilon }$ there exists a ${\displaystyle k_{0}}$ such for all ${\displaystyle k>k_{0}}$, ${\displaystyle \|f(k)-f_{\infty }\|<\epsilon }$. The most basic proof technique is to find such a ${\displaystyle k_{0}}$ and prove the required inequality. If the value of ${\displaystyle f_{\infty }}$ is not known in advance, the techniques below may be useful.

Contraction mappings

In many cases, the function whose convergence is of interest has the form ${\displaystyle f(k+1)=T(f(k))}$ for some transformation ${\displaystyle T}$. For example, ${\displaystyle T}$ could map ${\displaystyle f(k)}$ to ${\displaystyle f(k+1)=Af(k)}$ for some conformable matrix ${\displaystyle A}$. Alternatively, ${\displaystyle T}$ may be an element-wise operation, such as replacing each element of ${\displaystyle f(k)}$ by the square root of its magnitude.

In such cases, if the problem satisfies the conditions of Banach fixed-point theorem (the domain is a non-empty complete metric space) then it is sufficient to prove that ${\displaystyle \|T(x)-T(y)\|<\|k(x-y)\|}$ for some constant ${\displaystyle |k|<1}$ which is fixed for all ${\displaystyle x}$ and ${\displaystyle y}$. Such a ${\displaystyle T}$ is called a contraction mapping. The composition of two contraction mappings is a contraction mapping, so if ${\displaystyle T=T_{1}\circ T_{2}}$, then it is sufficient to show that ${\displaystyle T_{1}}$ and ${\displaystyle T_{2}}$ are both contraction mappings.

Example

Famous example of the use of this approach include

• If ${\displaystyle T}$ has the form ${\displaystyle T(x)=Ax+B}$ for some matrices ${\displaystyle A}$ and ${\displaystyle B}$, then convergence to ${\displaystyle (I-A)^{-1}B}$ occurs if the magnitudes of all eigenvalues of ${\displaystyle A}$ are less than 1^{[ citation needed ]}.

Non-expansion mappings

If both above inequalities are weak (${\displaystyle k\leq 1}$), the mapping is a non-expansion mapping. It is not sufficient for ${\displaystyle T}$ to be a non-expansion mapping. For example, ${\displaystyle T(x)=-x}$ is a non-expansion mapping, but the sequence does not converge. However, the composition of a contraction mapping and a non-expansion mapping (or vice versa) is a contraction mapping.

Contraction mappings on limited domains

If ${\displaystyle T}$ is not a contraction mapping on its entire domain, but it is on its codomain (the image of the domain), that is also sufficient for convergence. This also applies for decompositions. For example, consider ${\displaystyle T(x)=\cos(\sin(x))}$. The function ${\displaystyle \cos }$ is not a contraction mapping, but it is on the restricted domain ${\displaystyle [-1,1]}$, which is the codomain of ${\displaystyle \sin }$ for real arguments. Since ${\displaystyle \sin }$ is a non-expansion mapping, this implies ${\displaystyle T}$ is a contraction mapping.

Convergent subsequences

Every bounded sequence in ${\displaystyle \mathbb {R} ^{n}}$ has a convergent subsequence, by the Bolzano–Weierstrass theorem. If these all have the same limit, then the original sequence converges to that limit. If it can be shown that all of the subsequences of ${\displaystyle f}$ have the same limit, such as by showing that there is a unique fixed point of the transformation ${\displaystyle T}$, then the initial sequence must also converge to that limit.

Monotonicity (Lyapunov functions)

Every bounded monotonic sequence in ${\displaystyle \mathbb {R} ^{n}}$ converges to a limit.

This approach can also be applied to sequences that are not monotonic. Instead, it is possible to define a function ${\displaystyle V:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ such that ${\displaystyle V(f(n))}$ is monotonic in ${\displaystyle n}$. If the ${\displaystyle V}$ satisfies the conditions to be a Lyapunov function then ${\displaystyle f}$ is convergent. Lyapunov's theorem is normally stated for ordinary differential equations, but can also be applied to sequences of iterates by replacing derivatives with discrete differences.

The basic requirements on ${\displaystyle V}$ are that

1. ${\displaystyle V(f(n+1))-V(f(n))<0}$ for ${\displaystyle f(n)\neq 0}$ and ${\displaystyle V(0)=0}$ (or ${\displaystyle {\dot {V}}(x)<0}$ for ${\displaystyle x\neq 0}$)
2. ${\displaystyle V(x)>0}$ for all ${\displaystyle x\neq 0}$ and ${\displaystyle V(0)=0}$
3. ${\displaystyle V}$ be "radially unbounded", so that ${\displaystyle V(x)}$ goes to infinity for any sequence with ${\displaystyle \|x\|}$ that tends to infinity.

In many cases, a Lyapunov function of the form ${\displaystyle V(x)=x^{T}Ax}$ can be found, although more complex forms are also used.

For delay differential equations, a similar approach applies with Lyapunov functions replaced by Lyapunov functionals also called Lyapunov-Krasovskii functionals.

If the inequality in the condition 1 is weak, LaSalle's invariance principle may be used.

Convergence of sequences of functions

To consider the convergence of sequences of functions, ^[2] it is necessary to define a distance between functions to replace the Euclidean norm. These often include

• Convergence in the norm (strong convergence) -- a function norm, such as ${\textstyle \|g\|_{f}=\int _{x\in A}\|g(x)\|dx}$ is defined, and convergence occurs if ${\displaystyle ||f(n)-f_{\infty }||_{f}\rightarrow 0}$. For this case, all of the above techniques can be applied with this function norm.
• Pointwise convergence -- convergence occurs if for each ${\displaystyle x}$, ${\displaystyle f_{n}(x)\rightarrow f_{\infty }(x)}$. For this case, the above techniques can be applied for each point ${\displaystyle x}$ with the norm appropriate for ${\displaystyle f(x)}$.
• uniform convergence -- In pointwise convergence, some (open) regions can converge arbitrarily slowly. With uniform convergence, there is a fixed convergence rate such that all points converge at least that fast. Formally, ${\displaystyle \lim _{n\to \infty }\,\sup\{\,\left|f_{n}(x)-f_{\infty }(x)\right|:x\in A\,\}=0,}$ where ${\displaystyle A}$ is the domain of each ${\displaystyle f_{n}}$.

See also

• Convergence of Fourier series

Convergence of random variables

Random variables ^[3] are more complicated than simple elements of ${\displaystyle \mathbb {R} ^{n}}$. (Formally, a random variable is a mapping ${\displaystyle x:\Omega \rightarrow V}$ from an event space ${\displaystyle \Omega }$ to a value space ${\displaystyle V}$. The value space may be ${\displaystyle \mathbb {R} ^{n}}$, such as the roll of a dice, and such a random variable is often spoken of informally as being in ${\displaystyle \mathbb {R} ^{n}}$, but convergence of sequence of random variables corresponds to convergence of the sequence of functions, or the distributions, rather than the sequence of values.)

There are multiple types of convergence, depending on how the distance between functions is measured.

• Convergence in distribution -- pointwise convergence of the distribution functions of the random variables to the limit
• Convergence in probability
• Almost sure convergence -- pointwise convergence of the mappings ${\displaystyle x_{n}:\Omega \rightarrow V}$ to the limit, except at a set in ${\displaystyle \Omega }$ with measure 0 in the limit.
• Convergence in the mean

Each has its own proof techniques, which are beyond the current scope of this article.

See also

• Dominated convergence
• Carleson's theorem establishing the pointwise (Lebesgue) almost everywhere convergence of Fourier series of L2 functions
• Doob's martingale convergence theorems a random variable analogue of the monotone convergence theorem

Topological convergence

For all of the above techniques, some form the basic analytic definition of convergence above applies. However, topology has its own definition of convergence. For example, in a non-hausdorff space, it is possible for a sequence to converge to multiple different limits.

References

1. Ross, Kenneth. Elementary Analysis: The Theory of Calculus. Springer.
2. Haase, Markus. Functional Analysis: An Elementary Introduction. American Mathematics Society.
3. Billingsley, Patrick (1995). Probability and Measure. John Wesley.