Monotony criterion – Serlo

In this chapter, we will prove that monotonous and bounded functions converge. So if you have a bounded sequence, which in addition is monotonous, you instantly know that it converges. There is no need ot make complicated bounds within the $\epsilon$-definition. You do not even have to know what the limit is!

This especially turns out to be useful for recursive sequences. For those sequences, there is often no explicit form available which makes it hard to guess, what a limit may be or what the difference of a sequence element to a potential limit is.

Convergence of monotonous and bounded sequences

Mediendatei abspielen

Convergence of monotonous and bounded functions. (YouTube-Video in German, by the channel Quatematik)

Theorem (Monotony criterion for sequences)

Every monotone and bounded sequence in the real numbers converges.

It is useful to get a visual representation of this theorem: Take a piece of paper and try draw a sequence of points, which is monotonously increasing and bounded, but still diverges. How could it possibly diverge. Maybe to $\pm \infty$? This is certainly not possible because the sequence is bounded. The only option left for a divergence is that the function "jumps" between different points. But now, monotony tells us that $a_{n+1}\geq a_{n}$ , so the sequence goes always up and never down. Therefore, "jumping" is also not allowed. The sequence either goes up until it reaches the upper bound (and hence converges to it), or it gets "stuck" before reaching the bound and converges to some smaller number (below the bound). So intuitively, there should be no way for the sequence to converge. Let us make this statement watertight by formulating it as a mathematical theorem:

Proof (Monotony criterion for sequences)

The sequence $a_{n}={\tfrac {n}{n+1}}$

We consider monotonously increasing sequences. The proof for monotonously decreasing sequences works analogously. Let $(a_{n})_{n\in \mathbb {N} }$ be a monotonously increasing and bounded function. We need to find a potential limit and then prove that the sequence actually converges to it (using the Epsilon-definition). To see, how this works, we first consider the sequence $a_{n}={\tfrac {n}{n+1}}$ as an example:

$a_{n}={\frac {n}{n+1}}={\frac {1}{1+{\frac {1}{n}}}}{\xrightarrow {n\to \infty }}1$

The limit is 1. And obviously, the sequence elements approach 1, but never reach it. So 1 is a supremum to the sequence elements $\left\{{\tfrac {n}{n+1}}:n\in \mathbb {N} \right\}$. For a general monotonous and bounded sequence $a_{n}$, we may also assume that it converges towards its supremum, since for convergence to a smaller number, the sequence would have to "go down again". So let us prove that $a_{n}$ converges to

$a=\sup\{a_{n}:n\in \mathbb {N} \}$

This supremum must exist, since $(a_{n})_{n\in \mathbb {N} }$ is bounded from above.

Now, let us turn to the convergence proof: Let $\epsilon >0$ be given. Depending on this $\epsilon$ we need to find an $N\in \mathbb {N}$ such that $|a_{n}-a|<\epsilon$ for all $n\geq N$ .

As $a$ is a supremum, we know that there is an $a_{N}$ , which is greater than $a-\epsilon$ . If this was not the case, $a-\epsilon$ would be an upper bound to the sequence (which can not be, since $a$ as a supremum is the smallest upper bound). Hence, there is

$a\geq a_{N}>a-\epsilon$

Which implies

$|a-a_{N}|<\epsilon$

So $a_{N}$ is close enough to $a$. But are all $a_{n}$ with $n\geq N$ also closer that $\epsilon$ to $a$? If the sequence was not monotonous, there would be no warranty for that and it might be "divergent by jumping around"! But our sequence is monotonously increasing, so all $a_{n}$ with $n\geq N$ must be bigger or equal to $a_{N}$ . In addition, $a\geq a_{n}$, since $a$ is an upper bound to the sequence. For $n\geq N$ we hence have

$a\geq a_{n}\geq a_{N}>a-\epsilon$

so

$|a-a_{n}|\leq |a-a_{N}|<\epsilon$

This finishes the proof of $a$ being the limit of $(a_{n})_{n\in \mathbb {N} }$ and the sequence converges. For monotonously decreasing sequences, the proof works analogously, choosing the infimum instead of the supremum.

An example

Exercise (Monotony criterion for sequences)

Show, using the monotony criterion, that the sequence $(a_{n})_{n\in \mathbb {N} }$ with

$a_{n}={\frac {1}{n}}+{\frac {1}{n+1}}+\ldots +{\frac {1}{2n}}=\sum _{k=n}^{2n}{\frac {1}{k}}$

converges .

Solution (Monotony criterion for sequences)

Step 1: Monotony of $(a_{n})_{n\in \mathbb {N} }$.

In order to apply the criterion, we need to make sure that $(a_{n})_{n\in \mathbb {N} }$ is monotonous. We have a sequence of sums and the difference between subsequent elements is

${\begin{aligned}a_{n+1}-a_{n}&=\sum _{k=n+1}^{2(n+1)}{\frac {1}{k}}-\sum _{k=n}^{2n}{\frac {1}{k}}\\[0.3em]&=\sum _{k=n+1}^{2(n+1)}{\frac {1}{k}}-\sum _{k=n}^{2n}{\frac {1}{k}}\\[0.3em]&=\sum _{k=n+1}^{2n+2}{\frac {1}{k}}-\sum _{k=n}^{2n}{\frac {1}{k}}\\[0.3em]&=\sum _{k=n+1}^{2n}{\frac {1}{k}}+{\frac {1}{2n+1}}+{\frac {1}{2n+2}}-\sum _{k=n}^{2n}{\frac {1}{k}}\\[0.3em]&=\sum _{k=n}^{2n}{\frac {1}{k}}-{\frac {1}{n}}+{\frac {1}{2n+1}}+{\frac {1}{2n+2}}-\sum _{k=n}^{2n}{\frac {1}{k}}\\[0.3em]&={\frac {1}{2n+1}}+{\frac {1}{2n+2}}-{\frac {1}{n}}\\[0.3em]&={\frac {(2n+2)n+(2n+1)n-(2n+1)(2n+2)}{(2n+1)(2n+2)n}}\\[0.3em]&={\frac {2n^{2}+2n+2n^{2}+n-4n^{2}-6n-2}{n(2n+1)(2n+2)}}\\[0.3em]&={\frac {-3n-2}{n(2n+1)(2n+2)}}\\[0.3em]&{\color {Gray}\left\downarrow \ -3n-2\leq 0{\text{ und }}n(2n+1)(2n+2)\geq 0\right.}\\[0.3em]&\leq 0\end{aligned}}$

I.e. $a_{n+1}\leq a_{n}$ for all $n\in \mathbb {N}$ and $(a_{n})_{n\in \mathbb {N} }$ is monotonously decreasing.

Step 2: Boundedness of $(a_{n})_{n\in \mathbb {N} }$

Since $(a_{n})_{n\in \mathbb {N} }$ decreases monotonously, we need to show that it is bounded from below This is very easy to see: all summands are $\geq 0$, so the sequence elements are also $\geq 0$. In order to find out what the potential limit is, we can try to even find a better (= higher) lower bound:

${\begin{aligned}a_{n}&={\frac {1}{n}}+{\frac {1}{n+1}}+\ldots +{\frac {1}{2n}}\\[0.3em]&{\color {Gray}\left\downarrow \ n,n+1,\ldots ,2n\leq 2n\iff {\frac {1}{n}},{\frac {1}{n+1}},\ldots {\frac {1}{2n}}\geq {\frac {1}{2n}}\right.}\\[0.3em]&\geq \underbrace {{\frac {1}{2n}}+{\frac {1}{2n}}+\ldots +{\frac {1}{2n}}} _{(n+1){\text{-mal}}}\\[0.3em]&={\frac {n+1}{2n}}\\[0.3em]&={\frac {1+{\frac {1}{n}}}{2}}\\[0.3em]&{\color {Gray}\left\downarrow \ {\frac {1}{n}}\geq 0\right.}\\[0.3em]&\geq {\frac {1}{2}}\end{aligned}}$

So $(a_{n})_{n\in \mathbb {N} }$ (and also its limit) is bounded from below by ${\tfrac {1}{2}}=0.5$.

Hence, the monotony criterion can be applied and $(a_{n})_{n\in \mathbb {N} }$ converges.

Hint

Later, we will actually be able to show that the limit is $\lim \limits _{n\to \infty }\sum \limits _{k=n}^{2n}{\tfrac {1}{k}}=\ln(2)\approx 0.693$.

Nested intervals

There is a useful implication for nested intervals.

Recap: A sequence of nested intervals is a sequence $(I_{n})_{n\in \mathbb {N} }=([a_{n},b_{n}])_{n\in \mathbb {N} }$ with the following properties:

1. All intervals are subsets of their precursors:

$\forall n\in \mathbb {N} :I_{n+1}\subseteq I_{n}$

2. For all $\epsilon >0$ there is an interval $I_{N}$ smaller than $\epsilon$:

$\forall \epsilon \in \mathbb {R} ^{+}:\exists N\in \mathbb {N} :b_{N}-a_{N}<\epsilon$

In that case, there is always exactly one real number being included in all intervals. This statement can be shown using the monotony criterion:

We take a look at the two sequences $(a_{n})_{n\in \mathbb {N} }$ and $(b_{n})_{n\in \mathbb {N} }$, i.e. upper and lower bounds of the intervals.

• Since $[a_{1},b_{1}]\supseteq [a_{2},b_{2}]\supseteq [a_{3},b_{3}]\supseteq \ldots \supseteq [a_{n},b_{n}]$ there is

$a_{1}\leq a_{2}\leq a_{3}\leq \ldots \leq a_{n}$, i.e. $a_{n-1}\leq a_{n}$, and $b_{1}\geq b_{2}\geq b_{3}\geq \ldots \geq b_{n}$, i.e. $b_{n-1}\geq b_{n}$

So $(a_{n})$ is monotonously increasing and $(b_{n})$ monotonously decreasing.

• Since $a_{n}\leq b_{1}$ and $b_{n}\geq a_{1}$ , the sequence $(a_{n})$ is bounded from above by $b_{1}$ and conversely, $(b_{n})$ is bounded from below by $a_{1}$ .

The monotony criterion hence implies that $(a_{n})$ and $(b_{n})$ converge. The limit of both is even equal and exactly this one number being in all intervals:

Since $(I_{n})_{n\in \mathbb {N} }$ is a sequence of nested intervals, there is

$\forall \epsilon >0\ \exists N\in \mathbb {N} :b_{N}-a_{N}<\epsilon$

As $I_{n+1}\subseteq I_{n}$ we also have $b_{n}-a_{n}<\epsilon$ for all $n\geq N$.

So the difference of $(a_{n})$ and $(b_{n})$ converges to0:

$\forall \epsilon >0\ \exists N\in \mathbb {N} \ \forall n\geq N:|b_{n}-a_{n}|=b_{n}-a_{n}<\epsilon$

Using the limit theorems, we hence get that $(a_{n})$ and $(b_{n})$ have the same limit. This limit is

$a=\sup\{a_{n}:n\in \mathbb {N} \}=\inf\{b_{n}:n\in \mathbb {N} \}$

So $a_{n}\leq a\leq b_{n}$ , i.e. $a\in [a_{n},b_{n}]$ and $a$ is included in all intervals. All other real numbers $a+\epsilon$ or $a-\epsilon$ with $\epsilon >0$ can not be inside all intervals, since they either exceed $a$ as an upper bound or as a lower bound. More precisely, for $a+\epsilon$, there is a $b_{n}<a+\epsilon$ and $a+\epsilon$ is not inside the interval $[a_{n},b_{n}]$. An analogous problem appears for $a_{n}>a-\epsilon$. So there is exactly one real number $a$ included in all intervals.

We recap those considerations in a theorem:

Theorem

Let $(I_{n})_{n\in \mathbb {N} }=([a_{n},b_{n}])_{n\in \mathbb {N} }$ be a sequence of nested intervals. Then, $(a_{n})_{n\in \mathbb {N} }$ and $(b_{n})_{n\in \mathbb {N} }$ both converge to one limit

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }b_{n}=x.$

and $x$ is the only real number with $x\in I_{n}\forall n\in \mathbb {N}$

Application: Euler's number

Computing Euler's number e by nested intervals

We consider the sequence of intervals $(I_{n})_{n\in \mathbb {N} }=([a_{n},b_{n}])_{n\in \mathbb {N} }$ with $a_{n}=\left(1+{\tfrac {1}{n}}\right)^{n}$ and $b_{n}=\left(1+{\tfrac {1}{n}}\right)^{n+1}$.

These can be shown to be nested intervals, which we will do in the following. In that case, both $(a_{n})_{n\in \mathbb {N} }$ and $(b_{n})_{n\in \mathbb {N} }$ converge. At first,

$b_{n}=\left(1+{\tfrac {1}{n}}\right)^{n+1}=\underbrace {\left(1+{\tfrac {1}{n}}\right)^{n}} _{=a_{n}}\cdot \underbrace {\left(1+{\tfrac {1}{n}}\right)} _{\geq 1}\geq a_{n}$

So $(I_{n})=([a_{n},b_{n}])$ is well-defined.

For a sequence of nested intervals, we need to establish two properties. At first, for all $n\in \mathbb {N}$: $I_{n+1}\subseteq I_{n}$ (intervals are included in each other). This is done in two steps:

• The lower bounds $(a_{n})$are monotonously increasing, i.e. $a_{n+1}\geq a_{n}$. This is done by showing ${\tfrac {a_{n+1}}{a_{n}}}\geq 1$ , using Bernoulli's inequality:

${\begin{aligned}{\frac {a_{n+1}}{a_{n}}}&={\frac {\left(1+{\tfrac {1}{n+1}}\right)^{n+1}}{\left(1+{\tfrac {1}{n}}\right)^{n}}}\\[0.5em]&={\frac {\left(1+{\tfrac {1}{n+1}}\right)^{n+1}}{\left(1+{\tfrac {1}{n}}\right)^{n+1}}}\cdot \left(1+{\tfrac {1}{n}}\right)\\[0.5em]&={\frac {\left({\tfrac {n+2}{n+1}}\right)^{n+1}}{\left({\tfrac {n+1}{n}}\right)^{n+1}}}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left({\tfrac {\tfrac {n+2}{n+1}}{\tfrac {n+1}{n}}}\right)^{n+1}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left({\tfrac {n(n+2)}{(n+1)^{2}}}\right)^{n+1}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left({\tfrac {n^{2}+2n+1-1}{(n+1)^{2}}}\right)^{n+1}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left({\tfrac {(n+1)^{2}-1}{(n+1)^{2}}}\right)^{n+1}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left(1-{\tfrac {1}{(n+1)^{2}}}\right)^{n+1}\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&\ \left\downarrow {\text{ Bernoulli's inequality}}\right.\\[0.5em]&\geq \left(1-{\tfrac {n+1}{(n+1)^{2}}}\right)\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left(1-{\tfrac {1}{n+1}}\right)\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=\left({\tfrac {n}{n+1}}\right)\cdot \left({\tfrac {n+1}{n}}\right)\\[0.5em]&=1\end{aligned}}$

• The upper bounds $(b_{n})$ are monotonously increasing, i.e. $b_{n+1}\leq b_{n}$.

Exercise

Prove this.

How to get to the proof?

The proof works analogously to the case above with ${\tfrac {b_{n}}{b_{n+1}}}\geq 1$:

Proof

${\begin{aligned}{\frac {b_{n}}{b_{n+1}}}&={\frac {\left(1+{\tfrac {1}{n}}\right)^{n+1}}{\left(1+{\tfrac {1}{n+1}}\right)^{n+2}}}\\[0.5em]&={\frac {\left(1+{\tfrac {1}{n}}\right)^{n+2}}{\left(1+{\tfrac {1}{n+1}}\right)^{n+2}}}\cdot {\tfrac {1}{\left(1+{\tfrac {1}{n}}\right)}}\\[0.5em]&={\frac {\left({\tfrac {n+1}{n}}\right)^{n+2}}{\left({\tfrac {n+2}{n+1}}\right)^{n+2}}}\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left({\tfrac {(n+1)^{2}}{n(n+2)}}\right)^{n+2}\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left({\tfrac {n^{2}+2n+1}{n(n+2)}}\right)^{n+2}\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left({\tfrac {n(n+2)+1}{n(n+2)}}\right)^{n+2}\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left(1+{\tfrac {1}{n(n+2)}}\right)^{n+2}\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&\ \left\downarrow {\text{ Bernoulli's inequality}}\right.\\[0.5em]&\geq \left(1+{\tfrac {n+2}{n(n+2)}}\right)\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left(1+{\tfrac {1}{n}}\right)\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=\left({\tfrac {n+1}{n}}\right)\cdot \left({\tfrac {n}{n+1}}\right)\\[0.5em]&=1\end{aligned}}$

Since $(a_{n})$is monotonously increasing and $(b_{n})$ decreasing, the intervals are included in each other, i.e. $I_{n+1}=[a_{n+1},b_{n+1}]\subseteq [a_{n},b_{n}]=I_{n}$. So we have established the first property for nested intervals.

The second property is that interval sizes go to 0:

$\forall \epsilon >0\exists N\in \mathbb {N} :b_{N}-a_{N}<\epsilon$

This works by bounding $b_{N}-a_{N}$ from above.

${\begin{aligned}b_{N}-a_{N}&=\left(1+{\tfrac {1}{N}}\right)^{N+1}-\left(1+{\tfrac {1}{N}}\right)^{N}\\&=\left(1+{\tfrac {1}{N}}\right)^{N}\cdot \left[\left(1+{\frac {1}{N}}\right)-1\right]\\&=a_{N}\cdot {\frac {1}{N}}.\end{aligned}}$

But now, $a_{N}\leq b_{N}\leq b_{1}=\left(1+{\frac {1}{1}}\right)^{2}=4$, so

$b_{N}-a_{N}=a_{N}\cdot {\tfrac {1}{N}}\leq 4\cdot {\tfrac {1}{N}}={\tfrac {4}{N}}$

There is ${\tfrac {4}{N}}<\epsilon \Leftrightarrow N>{\tfrac {4}{\epsilon }}$. If we are given any $\epsilon >0$ and choose a corresponding $N\in \mathbb {N}$ with $N>{\tfrac {4}{\epsilon }}$, then

$b_{N}-a_{N}\leq {\frac {4}{N}}<\epsilon$

So the second property is also established and $(I_{n})$ is indeed a sequence of nested intervals. The number included in all intervals is called Euler's number $e$. The sequence of nested intervals can be used for making estimates, what $e$ is. For instance, $e\in [a_{10},b_{10}]=[2.59374246,2.85311671]$. For greater $n$, one would get even more digits, e.g. $e\approx 2,718281828459045$.

With the theorem above, there is

$\lim _{n\to \infty }\left(1+{\tfrac {1}{n}}\right)^{n}=e=\lim _{n\to \infty }\left(1+{\tfrac {1}{n}}\right)^{n+1}.$

In the series chapter, we will show that $e=\exp(1)$ with $\exp$ denoting the exponential series.