7.8 Bounded Monotonic Sequences

7.87   Theorem. Let $\{[a_n,b_n]\}$ be a binary search sequence in $\mbox{{\bf R}}$. Suppose $\{[a_n,b_n]\} \to c$ where $c\in\mbox{{\bf R}}$.Then $\{b_n-a_n\}$ is a null sequence. Also $\{a_n\} \to c$ and $\{b_n\} \to c$.

Proof: We know that $${b_n - a_n = {b_0 - a_0 \over 2^n}}$$, and that $\{{1\over 2^n}\}$ is a null sequence, so $\{b_n-a_n\}$ is a null sequence. Since $\{[a_n,b_n]\} \to c$ we know that $a_n \leq c \leq b_n$ for all $n\in\mbox{{\bf N}}$, and hence

$$0 \leq \vert b_n - c\vert \leq \vert b_n - a_n\vert \hspace{.... ...space{.5in} 0 \leq \vert c - a_n\vert \leq \vert b_n - a_n\vert$$

for all $n\in\mbox{{\bf N}}$. By the comparison theorem for null sequences it follows that $\{c-a_n\}$ and $\{b_n-c\}$ are null sequences, and hence $\{a_n\} \to c$ and $\{b_n\} \to c.$ $\mid\!\mid\!\mid$

7.88   Definition (Increasing, decreasing, monotonic) Let $f$ be a real sequence. We say $f$ is increasing if $f(n)\leq f(n+1)$ for all $n\in\mbox{{\bf N}}$, and we say $f$ is decreasing if $f(n)\geq f(n+1)$ for all $n\in\mbox{{\bf N}}$. We say that $f$ is monotonic if either $f$ is increasing or $f$ is decreasing.

7.89   Theorem. Let $f$ be an increasing real sequence. Then for all $k,n\in\mbox{{\bf N}}$

$$f(k) \leq f(k+n).$$

Proof: Define a proposition form $P$ on $\mbox{{\bf N}}$ by

$$P(n) = \lq\lq\mbox{for all }k\in\mbox{{\bf N}}( f(k) \leq f(k+n ))'', \mbox{ for all }n\in\mbox{{\bf N}}.$$

Then $P(0)$ says ``for all $k\in\mbox{{\bf N}}(f(k) \leq f(k))$'', so $P(0)$ is true. Since $f$ is increasing, we have for all $n\in\mbox{{\bf N}}$,

$$\begin{eqnarray*} P(n) &\mbox{$\Longrightarrow$}& \mbox{ for all }k\in\mbox{{\bf... ...k) \leq f( k +(n+1)) \Big)\\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

By induction, we conclude that $P(n)$ is true for all $n\in\mbox{{\bf N}}$, i.e.

$$\mbox{ for all }n\in\mbox{{\bf N}}\Big(\mbox{for all }k\in\mbox{{\bf N}}(f(k) \leq f(k+n)) \Big).\mbox{ $\mid\!\mid\!\mid$}$$

7.90   Corollary. Let $f$ be an increasing real sequence. Then for all $k,n\in\mbox{{\bf N}}$,

$$k\leq n\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}f(k)\leq f(n).$$ (7.91)

Proof: For all $k,n\in\mbox{{\bf N}}$

$$k \leq n \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n-k ... ...ce{1ex}$}f(k) \leq f(k+(n-k)) = f(n).\mbox{ $\mid\!\mid\!\mid$}$$

7.92   Definition (Upper bound, lower bound.) Let $f$ be a real sequence. We say that $f$ has an upper bound if there is a number $U\in\mbox{{\bf R}}$ such that $f(n) \leq U$ for all $n\in\mbox{{\bf N}}$. Any such number $U$ is called an upper bound for $f$. We say that $f$ has a lower bound if there is a number $L\in\mbox{{\bf R}}$ such that $L \leq f(n)$ for all $n\in\mbox{{\bf N}}$. Any such number $L$ is called a lower bound for $f$.

7.93   Examples. If $f(n) = {(-1)^n n\over n+1}$ for all $n\in\mbox{{\bf N}}$ then $1$ (or any number greater than $1$) is an upper bound for $f$, and $-1$ (or any number less than $-1$) is a lower bound for $f$. The sequence $g: n \mapsto n$ has no upper bound, but $0$ is a lower bound for $g$.

7.94   Exercise. A In definition 7.41, we defined a complex sequence $f$ to bounded if there is a number $B\in[0,\infty)$ such that $\vert f(n)\vert\leq B$ for all $n\in\mbox{{\bf N}}$. Show that a real sequence is bounded if and only if it has both an upper bound and a lower bound.

7.95   Theorem (Bounded monotonic sequences converge.)Let $f$ be
an increasing sequence in $\mbox{{\bf R}}$, and suppose $f$ has an upper bound. Then $f$ converges. (Similarly, decreasing sequences that have lower bounds converge.)

Proof: Let $B$ be an upper bound for $f$. We will construct a binary search sequence $\{[a_n,b_n]\}$ satisfying the following two conditions:

i. For every $n\in\mbox{{\bf N}}$, $b_n$ is an upper bound for $f$,

ii. For every $n\in\mbox{{\bf N}}$, $a_n$ is not an upper bound for $f$.

Let

$$\begin{eqnarray*}[a_0,b_0]&=&[f(0) - 1,B]\cr [a_{n+1},b_{n+1}]&=& \cases{ \left[... ...ght] & if ${{a_n+b_n}\over 2}$\ is not an upper bound for $f$.} \end{eqnarray*}$$

A straightforward induction argument shows that $\{[a_n,b_n]\}$ satisfies conditions i) and ii).

Let $c$ be the number such that $\{[a_n,b_n]\} \to c$. I will show that $f\to c$.

We know that $\{b_n - a_n\}=\{ {b_0 - a_0 \over 2^n}\}$ is a null sequence. Let $N$ be a precision function for $\{b_n-a_n\}$, so that for all $\varepsilon\in\mbox{${\mbox{{\bf R}}}^{+}$}$,

$$n \geq N(\varepsilon) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}\vert b_n - a_n\vert < \varepsilon.$$

I will use $N$ to construct a precision function $K$ for $f - \tilde{c}$.

Let $\varepsilon\in\mbox{${\mbox{{\bf R}}}^{+}$}$. Since $a_{N(\varepsilon)}$ is not an upper bound for $f$, there is a number $K(\varepsilon) \in\mbox{{\bf N}}$ such that $f(K(\varepsilon)) > a_{N(\varepsilon)}$. By condition i), I know that $f(n) \leq b_{N(\varepsilon)}$ for all $n\in\mbox{{\bf N}}$. Hence, since $f$ is increasing, we have for all $n\in\mbox{{\bf N}}$:

$$\begin{eqnarray*} n \geq K(\varepsilon) & \mbox{$\Longrightarrow$}& a_{N(\vareps... ...rightarrow$}& f(n) \in [a_{N(\varepsilon)}, b_{N(\varepsilon)}]. \end{eqnarray*}$$

Since $\{[a_n,b_n]\} \to c$ we also have

$$c \in [a_{N(\varepsilon)},b_{N(\varepsilon)}].$$

Hence

$$\vert f(n) - c\vert \leq b_{N(\varepsilon)} - a_{N(\varepsilon)} < \varepsilon \mbox{ for all }n \geq K(\varepsilon).$$

This says that $K$ is a precision function for $\{ f(n)-c\}$, and hence $f\to c$ $\mid\!\mid\!\mid$

7.96   Corollary. Let $f$ be a real sequence. If $f$ has an upper bound, and there is some $N\in\mbox{{\bf N}}$ such that

$$f(n+1) \geq f(n) \mbox{ for all }n \in \mbox{{\bf Z}}_{\geq N}$$

then $f$ converges. Similarly, if $f$ has a lower bound, and there is some $N\in\mbox{{\bf N}}$ such that

$$f(n+1) \leq f(n) \mbox{ for all }n \in \mbox{{\bf Z}}_{\geq N}$$

then $f$ converges.

7.97   Example. Let $a\in\mbox{${\mbox{{\bf R}}}^{+}$}$. Define a sequence $\{x_n\}$ by

$$\begin{eqnarray*} x_0&=&a+1\\ x_{n+1}&=&{{x_n^2+a}\over {2x_n}}\mbox{ for all }n\in\mbox{{\bf N}}. \end{eqnarray*}$$

We have $x_n>0$ for all $n$. Suppose $\{x_n\}$ converges to a limit $L$. Since $2x_nx_{n+1} = x_n^2 + a$ for all $n\in\mbox{{\bf N}}$, we can use the translation theorem to show that

$$2L^2=2\lim\{x_n\}\lim\{x_{n+1}\}=\lim\{x_{n}^2 + a\}= L^2 + a,$$

so $2L^2=L^2+a$, and hence $L^2=a$, so $L$ must be $\pm\sqrt a$. Since $x_n\geq 0$ for all $n$, it follows from the inequality theorem that $L\geq 0$, and hence if $\{x_n\}$ converges, it must converge to $\sqrt a$. In order to show that $\{x_n\}$ converges, it is sufficient to show that $\{x_n\}$ is decreasing. (We've already noted that $0$ is a lower bound.)

Well,

$$x_n-x_{n+1}=x_n-{{x_n^2+a}\over {2x_n}}={{2x_n^2-x_n^2-a}\over {2x_n}}={{x_n^2-a}\over {2x_n}},$$

so if I can show that $x_n^2-a\geq 0$ for all $n\in\mbox{{\bf N}}$, then I'll know that $\{x_n\}$ is decreasing. Now

$$\begin{eqnarray*} x_{n+1}^2-a &=&\left({{x_n^2+a}\over {2x_n}}\right)^2 - a ={{x... ...a^2-4ax_n^2}\over {4x_n^2}}={{(x_n^2-a)^2}\over {4x_n^2}}\geq 0. \end{eqnarray*}$$

I also note that $x_0^2-a=a^2+a+1>0$, so I finally conclude that $\{x_n\}$ is decreasing, and hence $\{x_n\}\to\sqrt a$. In fact, this sequence converges very fast, and is the basis for the square root algorithm used on most computers.

7.98   Example ( $\{n^{1\over n}\}$) We will show that $\{n^{1\over n} \}_{n \geq 1} \to 1.$

Claim: $\{n^{1\over n}\}_{n \geq 3}$ is a decreasing sequence.

Proof: For all $n\in\mbox{{\bf Z}}_{\geq 1}$,

$$(n+1)^{1\over n+1} \leq n^{1\over n} \mbox{$\Longleftrightarrow$} (n+1)^n \leq n^{n+1} \mbox{{}}$$

$$\mbox{$\Longleftrightarrow$} \left({n+1 \over n}\right)^n \leq n.$$ (7.99)

We will show by induction that (7.99) holds for all $n \in \mbox{{\bf Z}}_{\geq 3}$. Let

$$P(n) = \mbox{\lq\lq }\left({n+1\over n}\right)^n \leq n\mbox{''} \mbox{ for all }n \in \mbox{{\bf Z}}_{\geq 3}.$$

Then $P(3)$ says $({4\over 3})^3 \leq 3$, which is true since $64<81$. For all $n \in \mbox{{\bf Z}}_{\geq 3}$,

$$\begin{eqnarray*} P(n) & \mbox{$\Longrightarrow$}& \left({n+1\over n}\right)^n \... ...}\right)^{n+1} \leq n+1 \\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

By induction, $P(n)$ is true for all $n \in \mbox{{\bf Z}}_{\geq 3}$, and the claim is proved.

Let $L = \lim\{ n^{1\over n} \}.$ Then $\{(2n)^{1\over 2n}\} \to L$, since any precision function for $\{n^{1\over n}\}$ is also a precision function for $\{(2n)^{1\over 2n}\}$. Hence

$$L^2 = \lim\{\Big( (2n)^{1\over 2n}\Big)^2\} = \lim\{2^{1\over n} n^{1\over n}\} = 1 \cdot L = L.$$

Thus $L^2 = L$, and hence $L \in \{0,1\}$. Since $n^{1\over n} \geq 1$ for all $n \in \mbox{{\bf Z}}_{\geq 3}$ it follows from the inequality theorem that $L \geq 1$, and hence $L=1.$ $\mid\!\mid\!\mid$

7.100   Exercise. A Show that the sequence

$$\left\{ {60^n \over n!}\right\} = \{ 1,60,1800,36000, \cdots\}$$

is a null sequence.

7.101   Exercise. Criticize the following argument.

We know that $${ \left\{ 1 + {1\over n} \right\}_{n\geq 1} \to 1+0 = 1}$$.

Hence $${ \left\{ \left(1 + {1\over n}\right)^n \right\}_{ n\geq 1} \to 1^n = 1.\mbox{ $\mid\!\mid\!\mid$}}$$

7.102   Note.I got the idea of using precision functions from a letter by Jan Mycielski in the Notices of the American Mathematical Society[34, p 569]. Mycielski calls precision functions Skolem functions.

The snowflake was introduced by Helge von Koch(1870-1924) who published his results in 1906 [32]. Koch considered only the part of the boundary corresponding to the bottom third of our polygon, which he introduced as an example of a curve not having a tangent at any point.

The sequence $g$ from Exercise 7.82 is taken from [12, page 55, ex 20]