# 5.7. Monotone and Bounded Sequences

In the last chapter the limit theorems provided a comfortable and quick method to decide on the convergence of a sequence. They are however applicable to only a small fraction of sequences as they have to meet a certain structure. So it is quite sensible to look for further covergence criterions.

We take up again monotony and boundedness. Considered separately both properties are not or only sparsely related to convergence. Combining them surprisingly leads us to a new and useful criterion. Compared to the limit theorems however there is a slight disadvantage as we won't get any information on the value of the limit. Luckily there are some tricks to overcome this insufficiency. Furthermore the new criterion is only valid in the reals and not applicable with sequences e.g. in $ℚ$ (cf. [5.7.11]).

Theorem:  For every sequence $\left({a}_{n}\right)$ in $ℝ$ we have:

 If $\left({a}_{n}\right)$ is monotone and bounded then $\left({a}_{n}\right)$ is convergent. [5.7.1]

Proof:  We assume $\left({a}_{n}\right)$ to be increasing. Due to boundedness we find an $s\in ℝ$ such that

.

Thus the set of all sequence members $\left\{{a}_{n}|n\in {ℕ}^{\ast }\right\}$ is a nonempty, bounded above subset of $ℝ$. According to the completeness axiom - and this is why this theorem is subject to the reals - this set has a least upper bound, its supremum. We set  $g≔\mathrm{sup}\left\{{a}_{n}|n\in {ℕ}^{\ast }\right\}$  and prove:

${a}_{n}\to g$

Let $\epsilon >0$ be given. As g is the least upper bound of $\left\{{a}_{n}|n\in {ℕ}^{\ast }\right\}$ it is impossible for $g-\epsilon$ to be an upper bound at all. Thus there is at least one sequence member above $g-\epsilon$, i.e. we have an ${n}_{0}\in {ℕ}^{\ast }$ such that ${a}_{{n}_{0}}>g-\epsilon$. Considering that g is a normal upper bound as well and that $\left({a}_{n}\right)$ is increasing we get for all $n\ge {n}_{0}$ :

$g-\epsilon <{a}_{{n}_{0}}\le {a}_{n}\le g,

i.e.  ${a}_{n}\in \right]g-\epsilon ,g+\epsilon \left[$. This proves our assertion according to [5.4.2].

Using the new criterion 'monotone and bounded' is always a two step task. First we solely prove the convergence and second calculate the limit.

Our first example classifies all the sequences of the $\left({q}^{n}\right)$ type.

Proposition:  With $q\in ℝ$ we have:

 $|q|<1⇒{q}^{n}\to 0$ [5.7.2]
 $|q|>1⇒\left({q}^{n}\right)$  is divergent [5.7.3]

Proof:
 1. ► Due to [5.5.6] it is sufficient to prove $|{q}^{n}|=|q{|}^{n}\to 0$, so we may assume $0\le q<1$. We multiply this inequality by ${q}^{n}$ and get . Thus $\left({q}^{n}\right)$ is decreasing and bounded, consequently convergent, say to g. For the remainder task, to prove $g=0$, we consider in addition the sequence $\left({q}^{n+1}\right)$, also converging to g. As a little trick we calculate the limit of $\left({q}^{n+1}\right)$ anew using the third limit theorem: $\begin{array}{l}{q}^{n+1}\to g\hfill \\ {q}^{n+1}=q\cdot {q}^{n}\to q\cdot g\hfill \end{array}$ From the uniqueness of g we know that  $g=q\cdot g⇔g\cdot \left(1-q\right)=0$  holds. So we have $g=0$ as $q\ne 1$ is our premise. 2. ► If $|q|>1$, say $|q|=1+x$  with an $x>0$ we deduce from the Bernoulli inequality: $|{q}^{n}|=|q{|}^{n}={\left(1+x\right)}^{n}\ge 1+nx$. $\left(1+nx\right)$ is unbounded and so is $\left({q}^{n}\right)$ and thus divergent.

Consider:

• The case $|q|=1$ is already well known: $\left({\left(-1\right)}^{n}\right)$ is divergent and ${1}^{n}=1\to 1$.

With the new criterion we can stock up the known convergences $\frac{1}{{n}^{k}}\to 0$.

Proposition:  For $r,s\in {ℕ}^{\ast }$ and  $q≔\frac{r}{s}$  the following holds:

 $\frac{1}{\sqrt[s]{n}}\to 0$ [5.7.4] $\frac{1}{{n}^{q}}\to 0$ [5.7.5]

Proof:
 1. ► As the root operator is monotone we have for all $n\in {ℕ}^{\ast }$: $\begin{array}{ll}\hfill & 1\le n\le n+1\hfill \\ ⇒\hfill & 1\le \sqrt[s]{n}\le \sqrt[s]{n+1}\hfill \\ ⇒\hfill & 1\ge \frac{1}{\sqrt[s]{n}}\ge \frac{1}{\sqrt[s]{n+1}}\ge 0\text{.}\hfill \end{array}$ From that we see that $\left(\frac{1}{\sqrt[s]{n}}\right)$ is decreasing and bounded thus convergent with a limit, say g. Again we calculate g using the third limit theorem: $\frac{1}{n}={\left(\frac{1}{\sqrt[s]{n}}\right)}^{s}\to {g}^{s}⇒{g}^{s}=0⇒g=0\text{.}$ 2. ► With the third limit theorem the result is immediate from 1.: $\frac{1}{{n}^{q}}=\frac{1}{{n}^{\frac{r}{s}}}={\left(\frac{1}{\sqrt[s]{n}}\right)}^{r}\to {0}^{r}=0\text{.}$

The next example is a classical one. It introduces one of the most important mathematical constants, the number e.

Example:

 $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ and  $\left({\left(1+\frac{1}{n}\right)}^{n+1}\right)$ are convergent. [5.7.6]

Proof:  Both assertions are best proved simultaneously. We need three steps to show that each sequence is monotone and bounded.
 1. ► $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ is increasing, because from the Bernoulli inequality we get for $n\in {ℕ}^{\ast }$ ${\left(1+\frac{1}{n+1}\right)}^{n+1}\cdot {\left(1-\frac{1}{n+1}\right)}^{n+1}={\left(1-\frac{1}{{\left(n+1\right)}^{2}}\right)}^{n+1}\ge 1-\frac{1}{n+1}$ and thus have: ${\left(1+\frac{1}{n+1}\right)}^{n+1}\ge \frac{1}{{\left(1-\frac{1}{n+1}\right)}^{n}}={\left(\frac{n+1}{n}\right)}^{n}={\left(1+\frac{1}{n}\right)}^{n}$. 2. ► $\left({\left(1+\frac{1}{n}\right)}^{n+1}\right)$ is decreasing: Again we employ the Bernoulli inequality for $n\in {ℕ}^{\ast }$ to get ${\left(\frac{{\left(n+1\right)}^{2}}{{\left(n+1\right)}^{2}-1}\right)}^{n+1}={\left(1+\frac{1}{{\left(n+1\right)}^{2}-1}\right)}^{n+1}\ge {\left(1+\frac{1}{{\left(n+1\right)}^{2}}\right)}^{n+1}\ge 1+\frac{1}{n+1}\text{.}$ This allows the following estimate: $\begin{array}{ll}{\left(1+\frac{1}{n+1}\right)}^{n+2}\hfill & \le {\left(\frac{{\left(n+1\right)}^{2}}{{\left(n+1\right)}^{2}-1}\right)}^{n+1}\cdot {\left(1+\frac{1}{n+1}\right)}^{n+1}\hfill \\ \hfill & ={\left(\frac{{\left(n+1\right)}^{2}}{\left(n+2\right)n}\cdot \frac{n+2}{n+1}\right)}^{n+1}\hfill \\ \hfill & ={\left(\frac{n+1}{n}\right)}^{n+1}\hfill \\ \hfill & ={\left(1+\frac{1}{n}\right)}^{n+1}\text{.}\hfill \end{array}$ 3. ► $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ and  $\left({\left(1+\frac{1}{n}\right)}^{n+1}\right)$ are bounded. As ${\left(1+\frac{1}{1}\right)}^{1}=2$ and ${\left(1+\frac{1}{1}\right)}^{2}=4$ the just proven monotony implies: $2\le {\left(1+\frac{1}{n}\right)}^{n}\le {\left(1+\frac{1}{n}\right)}^{n+1}\le 4$.

Consider:

• The convergence ${\left(1+\frac{1}{n}\right)}^{n+1}-{\left(1+\frac{1}{n}\right)}^{n}={\left(1+\frac{1}{n}\right)}^{n}\cdot \frac{1}{n}\to 0$ shows that in addition to [5.7.6] $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ and  $\left({\left(1+\frac{1}{n}\right)}^{n+1}\right)$ have the same limit! Leonhard Euler denoted this limit by the symbol  e :

 $e≔\mathrm{lim}{\left(1+\frac{1}{n}\right)}^{n}=\mathrm{lim}{\left(1+\frac{1}{n}\right)}^{n+1}$ [5.7.7]

We will encounter the number e some more times in the sequel and provide other calculations than [5.7.7]. Euler himself published the first 18 decimal places of e 1748 in his Introductio in Analysin infinitorum

e = 2.718281828459045235....

Certainly Euler didn't use the representation in [5.7.7] for his calculation as the convergence is rather slow. For $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ e.g. this can be checked interactively with the following applet. Take

(This applet operates on so called constructive real numbers and in theory can display arbitrary many decimal places. Though the default of 100 places could be replaced
by e.g.  with a
one should keep in mind that the actual work station is a limiting factor. Problems are not unlikely to occur with more than 3000 decimal places!)

The section after next will provide a sequence that converges to e markedly speedy. This sequence also will serve to prove that e is irrational.

Using the boundedness of $\left({\left(1+\frac{1}{n}\right)}^{n}\right)$ e.g. above by 4 enables us to prove the convergence of another, non-elementary sequence.

Example:

 $\sqrt[n]{n}\to 1$ [5.7.8]

Proof:  As ${\left(1+\frac{1}{n}\right)}^{n}\le 4$ the following assertions hold for each $n\ge 4$:

$\begin{array}{c}{\left(1+\frac{1}{n}\right)}^{n}\le n\\ n+1\le n\cdot \sqrt[n]{n}=\sqrt[n]{{n}^{n+1}}\\ \sqrt[n+1]{n+1}\le \sqrt[n]{n}\text{.}\end{array}$

Therefor ${\left(\sqrt[n]{n}\right)}_{n\ge 4}$ is decreasing and, because of $1\le \sqrt[n]{n}$, bounded as well thus convergent to a number $g\ge 1$. The case $g>1$ however is impossible: The ordering of $ℝ$ is archimedic, so for every $x>0$ there is an $n\in {ℕ}^{\ge 4}$ such that $1<\left(n-1\right)\cdot \frac{{x}^{2}}{2}$. The generalized binomial theorem [5.2.5] now allows the following estimate for this n:

$n.

So we have $\sqrt[n]{n}<1+x$ and thus $1+x\ne g$, considering that  $\sqrt[n]{n}\ge g$.

The convergence of $\left(\sqrt[n]{n}\right)$ entails in further results. For $1\le a\le n$ we have $1\le \sqrt[n]{a}\le \sqrt[n]{n}$ so the nesting theorem [5.5.8] provides

 $\sqrt[n]{a}\to 1$ [5.7.9]

From that the same is also true for  $0$\sqrt[n]{a}=\frac{1}{\sqrt[n]{\frac{1}{a}}}\to \frac{1}{1}=1$.

The remainder examples now emphasize on the importance of the 'monotone and bounded' criterion for recursive sequences.

 Example:   Let ${a}_{1}≔2\wedge {a}_{n+1}≔\frac{2{a}_{n}}{{a}_{n}+1}$  generate the recursive sequence $\left({a}_{n}\right)$. We have:  ${a}_{n}\to 1$. Proof:  First we show by induction  , which in fact means that $\left({a}_{n}\right)$ is already bounded. ►   ►   From $1\le {a}_{n}\le 2$ we can estimate $1=\frac{2{a}_{n}}{{a}_{n}+{a}_{n}}\le \frac{2{a}_{n}}{{a}_{n}+1}\le \frac{2\cdot 2}{1+1}=2$ and thus have  $1\le {a}_{n+1}\le 2$. Furthermore $\left({a}_{n}\right)$ proves to be decreasing: Because ${a}_{n}\ge 1$ implies ${a}_{n}\left({a}_{n}-1\right)\ge 0$, the assertion holds due to the following equivalence: $\begin{array}{ll}\hfill & {a}_{n}\ge {a}_{n+1}\hfill \\ ⇔\hfill & {a}_{n}\ge \frac{2{a}_{n}}{{a}_{n}+1}\hfill \\ ⇔\hfill & {a}_{n}^{2}+{a}_{n}\ge 2{a}_{n}\hfill \\ ⇔\hfill & {a}_{n}^{2}-{a}_{n}\ge 0\hfill \\ ⇔\hfill & {a}_{n}\left({a}_{n}-1\right)\ge 0\text{.}\hfill \end{array}$ All in all $\left({a}_{n}\right)$ has a limit, say $g\in \left[1,2\right]$. But g is the limit of $\left({a}_{n+1}\right)$ as well, so we can calculate g using the limit theorems: $g←{a}_{n+1}=\frac{2{a}_{n}}{{a}_{n}+1}\to \frac{2g}{g+1}\text{.}$ As g is unique, g satisfies the equation  $g=\frac{2g}{g+1}$ . So we have (note that $g\in \left[1,2\right]$): ${g}^{2}+g=2g⇔g\left(g-1\right)=0⇔g=1\text{.}$

The example to follow is a valuable tool when calculating square roots approximatively. It is an ancient procedure as the name suggests.

Proposition (Babylonian Square Root Algorithm):  Let $a>0$ be arbitrary. For each initial value ${a}_{1}>0$ the recursive sequence $\left({a}_{n}\right)$ given by  ${a}_{n+1}≔\frac{1}{2}\left({a}_{n}+\frac{a}{{a}_{n}}\right)$  is convergent, more precise:

 ${a}_{n}\to \sqrt{a}$ [5.7.10]

Proof:  A simple inductive consideration shows that ${a}_{n}>0$ for all n. As squares are always positive we can argue as follows

$\begin{array}{ll}\hfill & 0\le {\left(\sqrt{{a}_{n}}-\sqrt{\frac{a}{{a}_{n}}}\right)}^{2}={a}_{n}-2\sqrt{a}+\frac{a}{{a}_{n}}\hfill \\ ⇒\hfill & 2\sqrt{a}\le {a}_{n}+\frac{a}{{a}_{n}}\hfill \\ ⇒\hfill & \sqrt{a}\le \frac{1}{2}\left({a}_{n}+\frac{a}{{a}_{n}}\right)\hfill \end{array}$

to get the estimate ${a}_{n+1}\ge \sqrt{a}$. Employing this result we get for $n\ge 2$ :

Thus $\left({a}_{n+1}\right)$ is decreasing and due to  $\sqrt{a}\le {a}_{n+1}\le {a}_{2}$  bounded as well and thus in fact convergent with a limit $g\ge \sqrt{a}>0$. As ${a}_{n}\to g$ is also true our 'standard trick' is applicable and from

$g←{a}_{n+1}=\frac{1}{2}\left({a}_{n}+\frac{a}{{a}_{n}}\right)\underset{g\ne 0}{\to }\frac{1}{2}\left(g+\frac{a}{g}\right)$

we calculate g like this:  $g=\frac{1}{2}\left(g+\frac{a}{g}\right)⇔2g=g+\frac{a}{g}⇔{g}^{2}=a⇔g=\sqrt{a}$.

Consider:

• The basic principle of the Babylonian algorithm is as simple as effective. The equivalence

${a}_{n}<\sqrt{a}⇔\frac{a}{{a}_{n}}>\frac{a}{\sqrt{a}}=\sqrt{a}$

says: If ${a}_{n}$ is too small (to big) then $\frac{a}{{a}_{n}}$ is too big (too small). In any way their arithmetic mean ${a}_{n+1}$ should be an even better estimate.

• If a is rational a simple proof by induction shows that $\left({a}_{n}\right)$ is a sequence in $ℚ$. In particular we have:

 There is a monotone and bounded sequence $\left({a}_{n}\right)$ in $ℚ$ converging to the irrational number $\sqrt{2}$. [5.7.11]

As the limit of $\left({a}_{n}\right)$ is unique we conclude that $\left({a}_{n}\right)$ is divergent in $ℚ$ !

• The Babylonian root algorithm converges rather quickly. Even with an unfavourable initial value only few iterations are needed to fix the first ten decimal places. Let's take the square root of to demonstrate this. First we choose ${a}_{1}=$  as initial value, then set the number of iteration loops to and finally start the algorithm:

 $n=$ ${a}_{n}=$

 5.6. 5.8.