Next: 8. Continuity
Up: 7. Complex Sequences
Previous: 7.7 The Translation Theorem
  Index
7.87
Theorem.
Let
be a binary search sequence in
.
Suppose
where
.Then
is a null sequence. Also
and
.
Proof: We know that
, and that
is a null sequence, so
is
a null sequence. Since
we know that
for all
, and hence
for all
. By the comparison theorem for null sequences
it follows that
and
are null sequences, and hence
and
7.88
Definition (Increasing, decreasing, monotonic)
Let
![$f$](img13.gif)
be a real sequence. We say
![$f$](img13.gif)
is
increasing if
![$f(n)\leq
f(n+1)$](img504.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
, and we say
![$f$](img13.gif)
is
decreasing if
![$f(n)\geq f(n+1)$](img505.gif)
for
all
![$n\in\mbox{{\bf N}}$](img9.gif)
.
We say that
![$f$](img13.gif)
is
monotonic if either
![$f$](img13.gif)
is increasing
or
![$f$](img13.gif)
is decreasing.
7.89
Theorem.
Let
be an increasing real sequence. Then
for all
Proof: Define a proposition form
on
by
Then
says ``for all
'', so
is true.
Since
is increasing, we have for all
,
By induction, we conclude that
is true for all
, i.e.
Proof: For all
7.92
Definition (Upper bound, lower bound.)
Let
![$f$](img13.gif)
be a real sequence. We say that
![$f$](img13.gif)
has an
upper bound
if there is a number
![$U\in\mbox{{\bf R}}$](img517.gif)
such that
![$f(n) \leq U$](img518.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
. Any such number
![$U$](img519.gif)
is called an
upper bound
for ![$f$](img13.gif)
.
We say that
![$f$](img13.gif)
has a
lower bound
if there is a number
![$L\in\mbox{{\bf R}}$](img432.gif)
such that
![$L \leq f(n)$](img520.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
.
Any such number
![$L$](img28.gif)
is called a
lower bound for ![$f$](img13.gif)
.
7.93
Examples.
If
![$f(n) = {(-1)^n n\over n+1}$](img521.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
then
![$1$](img522.gif)
(or any number greater than
![$1$](img522.gif)
) is an upper
bound for
![$f$](img13.gif)
, and
![$-1$](img523.gif)
(or any number less than
![$-1$](img523.gif)
)
is a lower bound for
![$f$](img13.gif)
. The sequence
![$g: n \mapsto n$](img524.gif)
has no upper bound, but
![$0$](img34.gif)
is a lower bound for
![$g$](img111.gif)
.
7.94
Exercise.
A
In definition
7.41,
we defined a complex
sequence
![$f$](img13.gif)
to bounded if there is a number
![$B\in[0,\infty)$](img256.gif)
such that
![$\vert f(n)\vert\leq B$](img335.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
. 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
be
an increasing sequence in
, and suppose
has an upper bound. Then
converges. (Similarly, decreasing sequences that have lower bounds converge.)
Proof: Let
be an upper bound for
. We will construct a binary search
sequence
satisfying the following two conditions:
i. For every
,
is an upper bound for
,
ii. For every
,
is not an upper bound for
.
Let
A straightforward induction argument shows that
satisfies conditions i) and ii).
Let
be the number such that
. I will show that
.
We know that
is a null sequence.
Let
be a precision function for
, so that for all
,
I will use
to construct a precision function
for
.
Let
. Since
is not an upper bound for
,
there is a number
such that
.
By condition i), I know that
for all
.
Hence, since
is increasing, we have
for all
:
Since
we also have
Hence
This says that
is a precision function for
, and hence
7.97
Example.
Let
![$a\in\mbox{${\mbox{{\bf R}}}^{+}$}$](img544.gif)
. Define a sequence
![$\{x_n\}$](img387.gif)
by
We have
![$x_n>0$](img546.gif)
for all
![$n$](img313.gif)
.
Suppose
![$\{x_n\}$](img387.gif)
converges to a limit
![$L$](img28.gif)
.
Since
![$2x_nx_{n+1} = x_n^2 + a$](img547.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
, we can use
the translation theorem to show that
so
![$2L^2=L^2+a$](img549.gif)
, and hence
![$L^2=a$](img550.gif)
, so
![$L$](img28.gif)
must be
![$\pm\sqrt a$](img551.gif)
. Since
![$x_n\geq 0$](img552.gif)
for all
![$n$](img313.gif)
, it follows from the inequality theorem that
![$L\geq 0$](img431.gif)
, and hence if
![$\{x_n\}$](img387.gif)
converges, it must converge to
![$\sqrt a$](img553.gif)
. In order to show that
![$\{x_n\}$](img387.gif)
converges, it is sufficient to show that
![$\{x_n\}$](img387.gif)
is decreasing. (We've already noted
that
![$0$](img34.gif)
is a lower bound.)
Well,
so if I can show that
![$x_n^2-a\geq 0$](img555.gif)
for all
![$n\in\mbox{{\bf N}}$](img9.gif)
, then I'll know that
![$\{x_n\}$](img387.gif)
is decreasing. Now
I also note that
![$x_0^2-a=a^2+a+1>0$](img557.gif)
, so I finally conclude that
![$\{x_n\}$](img387.gif)
is
decreasing, and hence
![$\{x_n\}\to\sqrt a$](img558.gif)
. In fact, this sequence converges very
fast, and is the basis for the square root algorithm used on most computers.
7.98
Example (
)
We will show that
Claim:
is a decreasing sequence.
Proof: For all
,
We will show by induction that (
7.99) holds for all
![$n \in \mbox{{\bf Z}}_{\geq 3}$](img566.gif)
.
Let
Then
![$P(3)$](img568.gif)
says
![$({4\over 3})^3 \leq 3$](img569.gif)
, which is true since
![$64<81$](img570.gif)
.
For all
![$n \in \mbox{{\bf Z}}_{\geq 3}$](img566.gif)
,
By induction,
![$P(n)$](img513.gif)
is true for all
![$n \in \mbox{{\bf Z}}_{\geq 3}$](img566.gif)
,
and the claim is proved.
Let
Then
, since any precision function for
is also a precision function for
.
Hence
Thus
![$L^2 = L$](img576.gif)
, and hence
![$L \in \{0,1\}$](img577.gif)
. Since
![$n^{1\over n} \geq 1$](img578.gif)
for all
![$n \in \mbox{{\bf Z}}_{\geq 3}$](img566.gif)
it follows from the inequality
theorem that
![$L \geq 1$](img579.gif)
, and hence
7.100
Exercise.
A
Show that
the sequence
is a null sequence.
7.101
Exercise.
Criticize the following argument.
We know that
.
Hence
![$\displaystyle { \left\{ \left(1 + {1\over n}\right)^n \right\}_{ n\geq 1} \to 1^n = 1.\mbox{ $\mid\!\mid\!\mid$}}$](img583.gif)
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
from Exercise 7.82 is taken from
[12, page 55, ex 20]
Next: 8. Continuity
Up: 7. Complex Sequences
Previous: 7.7 The Translation Theorem
  Index