5.1 Sequences and Search Sequences

5.1   Definition (Sequence.) Let $A$ be a set. A sequence in $A$ is a function $f\colon \mbox{{\bf N}}\to A$. I sometimes denote the sequence $f$ by $\{f(n)\}$ or $\{f(0),f(1),f(2),\cdots\}$. For example, if $f\colon\mbox{{\bf N}}\to\mbox{{\bf Q}}$ is defined by $${f(n)={1\over {n+1}}}$$, I might write

$$f=\left\{ {1\over {n+1}}\right\}=\left\{1,{1\over 2},{1\over 3},\cdots\right\}.$$

5.2   Warning. The notation $\{f(0),f(1),f(2),\cdots\}$ is always ambiguous. For example,

$$\{1,2,4,8,16,\cdots\}$$

might denote $\{2^n\}$. It might also denote $\{\phi(n)\}$ where $\phi(n)$ is the number of regions into which a circle is divided when all the segments joining the vertices of an inscribed regular $(n+1)$-gon are drawn.

5.3   Entertainment. Show that $\phi(4)=2^4$, but that it is not true that $\phi(n)=2^n$ for all $n\in\mbox{{\bf N}}$.

5.4   Warning. The notation for a sequence and a set are the same, but a sequence is not a set. For example, as sets,

$$\{1,2,3,4,5,6,\cdots\}=\{2,1,4,3,6,5,\cdots\}.$$

But as sequences,

$$\{1,2,3,4,5,6,\cdots\}\neq\{2,1,4,3,6,5,\cdots\}.$$

5.5   Notation ( $\mbox{{\bf Z}}_{\geq k}$) Recall from section 3.65, that If $k\in\mbox{{\bf Z}}$, then

$$\mbox{{\bf Z}}_{\geq k}=\{n\in\mbox{{\bf Z}}\colon n\geq k\}.$$

Thus, $\mbox{{\bf Z}}_{\geq 0}=\mbox{{\bf N}}$. Occasionally I will want to consider sequences whose domain is $\mbox{{\bf Z}}_{\geq k}$ where $k\neq 0$. I will denote such a sequence by

$$\{f(n)\}_{n\geq k}.$$

Hence, if

$$f=\{1,2,3,\cdots\},$$

then $f(n)=n+1$ for all $n\in\mbox{{\bf N}}$, and if

$$g=\{1,2,3,\cdots\}_{n\geq 1},$$

then $g(n)=n$ for all $n\in\mbox{{\bf Z}}_{\geq 1}$.

5.6   Remark. Most of the results we prove for sequences $\{f(n)\}$ have obvious analogues for sequences $\{f(n)\}_{n\geq k}$, and I will assume these analogues without explanation.

5.7   Examples. $\qquad$ $\{i^n\}=\{1,i,-1,-i,1,i,\cdots\}$ is a sequence in $\mbox{{\bf C}}_{\mathbf{Q}}$.

$$\left\{\left[ 0,{1\over n}\right]\right\}_{n\geq 1}=\left\{[0... ...ft[0,{1\over 2}\right],\left[0,{1\over 3}\right],\cdots\right\}$$

is a sequence of intervals in an ordered field $F$.

5.8   Definition (Open and closed intervals.) An interval $J$ in an ordered field is closed if it contains all of its endpoints. $J$ is open if it contains none of its endpoints. Thus,

$$\emptyset,[a,b],(-\infty,a],[a,\infty),(-\infty,\infty) \mbox{ are closed intervals. }$$

$$\emptyset,(a,b),(-\infty,a),(a,\infty),(-\infty,\infty) \mbox{ are open intervals. }$$

$$(a,b],[a,b) \mbox{ where } a<b\mbox{ are neither open nor closed. }$$

5.9   Definition (Binary search sequence.) Let $F$ be an ordered field. A binary search sequence $\{[a_n,b_n]\}$ in $F$ is a sequence of closed intervals with end points $a_n,b_n$ in $F$ such that

1)

$[a_{n+1},b_{n+1}]\subset [a_n,b_n]$ for all $n\in\mbox{{\bf N}}$, and

2)

$${b_n-a_n={{b_0-a_0}\over {2^n}}}$$ for all $n\in\mbox{{\bf N}}$.

Condition 1) is equivalent to

$$a_n\leq a_{n+1}\leq b_{n+1}\leq b_n \mbox{ for all } n\in\mbox{{\bf N}}.$$

5.10   Warning. Note that the intervals in a binary search sequence are closed. This will be important later.

5.11   Definition (Convergence of search sequence.) Let $F$ be an ordered field, let $\{[a_n,b_n]\}$ be a binary search sequence in $F$, and let $x\in F$. We say $\{[a_n,b_n]\}$ converges to $x$ and write $\{[a_n,b_n]\}\to x$ if $x\in[a_n,b_n]$ for all $n\in\mbox{{\bf N}}$. We say $\{[a_n,b_n]\}$ converges, if there is some $x\in F$ such that $\{[a_n,b_n]\}\to x$. We say $\{[a_n,b_n]\}$ diverges if there is no such $x$.

5.12   Example. Let $F$ be an ordered field. Then $${ \left\{\left[0,{1\over {2^n}}\right]\right\}}$$ is a binary search sequence and $${\left\{\left[0,{1\over {2^n}}\right]\right\}\to 0}$$.

5.13   Exercise. Let $F$ be an ordered field, let $a,b\in F$ with $a<b$. Let $${m={{a+b}\over 2}}$$. Show that

1)

$a<m<b.$

2)

$${ {{m-a}}={{b-m}}={1\over 2}(b-a)}.$$

(Conditions 1) and 2) say that $m$ is the midpoint of $a$ and $b$.)

5.14   Exercise. Let $F$ be an ordered field and let $a,b\in F$ with $a\leq b$ and let $c,d$ be points in $[a,b]$. Show that

$$\vert c-d\vert \leq b-a;$$

i.e., if two points lie in an interval then the distance between the points is less than or equal to the length of the interval.

5.15   Exercise. A Show that $2^n\geq n$ for all $n\in\mbox{{\bf N}}$.

5.16   Example (A divergent binary search sequence.) Define a binary search sequence $\{[a_n,b_n]\}$ in $\mbox{{\bf Q}}$ by the rules

$$\begin{eqnarray*}[a_0,b_0]&=& [1,2]. \cr [a_{n+1},b_{n+1}] &=& \cases{ \left[ a_... ...er 2},b_n\right] &if $\left({{a_n+b_n}\over 2}\right)^2 <2$.\cr} \end{eqnarray*}$$

Thus,

$${{a_0+b_0}\over 2}={{1+2}\over 2}={3\over 2}; \hspace{.2in}\l... ...>2, \mbox{ so }[a_1,b_1] = \left[ {2\over 2},{3\over 2}\right];$$

$${{a_1+b_1}\over 2}={{ {2\over 2}+{3\over 2}}\over 2} ={5\over... ...}<2, \mbox{ so } [a_2,b_2]=\left[ {5\over 4},{6\over 4}\right];$$

$${{a_2+b_2}\over 2}={{ {5\over 4}+{6\over 4}}\over 2}={{11}\ov... ...mbox{ so } [a_3,b_3]=\left[ {{11}\over 8},{{12}\over 8}\right].$$

Since $${ {{a_n+b_n}\over 2}}$$ is the midpoint of $[a_n,b_n]$, we have

$$[a_{n+1},b_{n+1}]\subset [a_n,b_n]$$

and

$$b_{n+1}-a_{n+1}={1\over 2}(b_n-a_n)$$ (5.17)

It follows from (5.17) that

$$b_n-a_n={1\over {2^n}}(b_0-a_0) \mbox{ for all } n\in\mbox{{\bf N}}.$$

Hence $\{[a_n,b_n]\}$ is a binary search sequence. For each $n\in\mbox{{\bf N}}$, let $P(n)$ be the proposition

$$P(n)=``a_n^2<2\leq b_n^2.''$$

Then $P(0)$ says $1^2<2\leq 2^2$, so $P(0)$ is true. Let $n\in\mbox{{\bf N}}$. If $${\left( {{a_n+b_n}\over 2}\right)^2\geq 2}$$, then

$$\begin{eqnarray*} P(n)&\mbox{$\Longrightarrow$}& a_n^2<2\leq b_n^2\mbox{$\hspace... ..._{n+1}^2< 2\leq b_{n+1}^2 \\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

If $${\left( {{a_n+b_n}\over 2}\right)^{\!\!2}<2}$$, then

$$\begin{eqnarray*} P(n)&\mbox{$\Longrightarrow$}& a_n^2<2\leq b_n^2\mbox{$\hspace... ..._{n+1}^2< 2\leq b_{n+1}^2 \\ &\mbox{$\Longrightarrow$}& P(n+1). \end{eqnarray*}$$

Hence, in all cases, $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, and by induction, $a_n^2<2\leq b_n^2$ for all $n\subset\mbox{{\bf N}}$. Since $x^2\neq 2$ for all $x\in\mbox{{\bf Q}}$, we have

$$a_n^2<2<b_n^2 \mbox{ for all } n\in\mbox{{\bf N}}.$$ (5.18)

I now will show that $\{[a_n,b_n]\}$ diverges. Suppose, in order to get a contradiction, that for some $x\in\mbox{{\bf Q}}$, $\{[a_n,b_n]\}\to x$. Then

$$0\leq a_n\leq x\leq b_n \mbox{ for all } n\in\mbox{{\bf N}},$$

so

$$a_n^2\leq x^2\leq b_n^2.$$

Combining this with (5.18), we get

$$\vert x^2-2\vert\leq b_n^2-a_n^2=(b_n-a_n)(b_n+a_n) \leq\left({b_0-a_0 \over 2^n}\right)(b_0+b_0)={4\over {2^n}}$$ (5.19)

for all $n\in\mbox{{\bf N}}$. Since $2$ is not a square in $\mbox{{\bf Q}}$, $x^2-2\neq 0$. Write $${ \vert x^2-2\vert={p\over q}}$$, where $p,q\in\mbox{{\bf Z}}_{\geq 1}$. Then

$$\mbox{ for all }n \in \mbox{{\bf N}},\; {p\over q}\leq {4\over {2^n}},$$

so

$$\mbox{ for all }n \in \mbox{{\bf N}},\; 2^n\leq {{4q}\over p}\leq 4q.$$

By exercise 5.15A, for all $n\in\mbox{{\bf N}}$,

$$n\leq 2^n\leq 4q.$$ (5.20)

Statement (5.20) is false when $n=4q+1$, and hence our assumption that $\{[a_n,b_n]\}\to x$ was false. $\mbox{ $\mid\!\mid\!\mid$}$