# Math for Non-Geeks/Monotonicity criterion

In this chapter, we will prove that monotone and bounded functions converge. So if you have a bounded sequence, which in addition is monotone, 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 monotone and bounded sequences

Theorem (Monotonicity 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 monotonically 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, monotonicity 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 (Monotonicity criterion for sequences)
We consider monotonically increasing sequences. The proof for monotonically decreasing sequences works analogously. Let $(a_{n})_{n\in \mathbb {N} }$ be a monotonically 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 monotone 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 monotone, there would be no warranty for that and it might be "divergent by jumping around"! But our sequence is monotonically 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 monotonically decreasing sequences, the proof works analogously, choosing the infimum instead of the supremum.

## An example

Math for Non-Geeks: Template:Aufgabe
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 monotonicity 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 monotonically increasing and $(b_{n})$ monotonically 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 monotonicity 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

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 monotonically 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 monotonically increasing, i.e. $b_{n+1}\leq b_{n}$.
Math for Non-Geeks: Template:Aufgabe Since $(a_{n})$is monotonically 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.