\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{latexsym}
%\usepackage{graphics}
\input{inputs/macros-course}

%\newcommand{\solution}[1]{}
\renewcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\kth}{\ensuremath{\mbox{th}}}
\newcommand{\kmod}[1]{\ensuremath{(\mathrm{mod\ }#1)}}
\newcommand{\ignore}[1]{}

\newcommand{\spac}{\vspace{4mm}}
\newcommand{\hspac}{\vspace{2mm}}

\begin{document}
\psol{6}{October 22, 1999 (3c corrected 12/14)}
%, edited 10/23}

\textbf{Required reading}: F97 Lecture Notes 7 (Section 1), F97 Lecture
Notes 8 (excluding Section 2.4).

\textbf{Additional references}: F97 Lecture Notes 7 (Section 2), 
F97 Lecture Notes 8 (Section 2.4), S99 Handout 18.

{\large
Remember to include a \textbf{collaboration statement} on the front page
of your solutions (see Handout 2, \emph{Course Information}).}


\begin{problems}

\problem \textbf{Well-orderings}

Prove that for any finite set $S$, $(P(S),\subseteq)$ is a
partially-ordered set and moreover, every nonempty subset of $P(S)$ has a
minimal element.  (Recall that $P(S)$ stands for the power set of $S$.
Also, from the notes on well-founded posets (S99, H18): A \emph{minimal}
element, $m$, in a partial order has the property that no element is
strictly below it.  That is, if $s \preceq m$, then $s = m$, for all $s$
in the partialy ordered set.  For example, the set of three sets
\[
\set{\set{0,1}, \set{0,2,3}, \set{0,1,2,3}}
\]
partially ordered by containment has two minimal elements, namely, the
first two.)

\solution{
We need to show that $\subseteq$ is reflexive, transitive, and
antisymmetric over the elements of $2^S$, and that every nonempty subset
of $P(S)$ has a minimal element.

Reflexive: $B\subseteq B$ since $B=B$.

Transitive: Assume $A\subseteq B$ and $B\subseteq C$.  Then $x\in
A\Rightarrow x\in B\Rightarrow x\in C$, so $A\subseteq C$.

Antisymmetric: If $A\subseteq B$ and $B\subseteq A$, then clearly they 
have the same elements, so $A=B$.

Let $\emptyset\neq T\subseteq P(S)$. 
Define $A=\{|B|:B\in T\}$. Now by the well ordering principle, $A$ has
a least element, say $a$ (since $A$ is a subset of natural numbers.) 
Pick $C\in T$ such that $|C|=a$. Then $C$ is a minimal element in $T$.

%Pick any element, say $T_0\in T$, 
%then if $T_0$ is
%a minimal element then we are done, otherwise assume $T_1\in T$, s.t. 
%$T_1\subset T_0$. If $T_1$ is a minimal element then we are done, otherwise
%pick an element $T_2\in T$ s.t. $T_2\subset T_1$. Notice that we cannot 
%continue
%this procedure an infinite number of times since $P(S)$ has finite cardinality,
%say $k$. Therefore in a finite number of steps, say $k_0\le k$, we pick set
%$T_{k_0}$ such that $\not\exists R\in T \cdot R\subset T_{k_0}$. That is 
%$T_{k_0}$ is a minimal element.
}

\problem \textbf{Terminating games}
% taken from spring 98

Consider the following game for two players.  The players alternate
moves.  A move consists of a pair $(x,y)$ of natural numbers, subject
to the constraint that no move may be $\geq$ to any previous move in
both coordinates.  The player who makes the $(0,0)$ move is the loser.

\bparts 

\ppart Identify a winning strategy for the first player, and argue its
correctness.

\solution{
The first player has two winning strategies:

\noindent
{\bf Strategy 1:} If the first player starts with $(1,1)$ then
whatever the second player picks, either $(0,n)$ or $(0,n)$ for some
$n$, the first player will respond with, respectively, $(n,0)$ or
$(0,n)$.  By symmetry, the first player will always have a move
whenever the second player had a move, except when the second player
picks $(0,0)$ and loses.

\noindent
{\bf Strategy 2:} The second winning strategy is slightly more tricky:
The first player starts by picking $(0,2)$,\footnote{Of course,
picking $(2,0)$ would be equivalent, and the following argument will
hold for it as well, with x and y coordinates replaced} and then:
\begin{itemize}
\item
If the 2nd player picks $(0,n)$ for any $n\geq{1}$, 1st player responds with
$(1,n-1)$.
\item
If the 2nd player picks $(1,n)$ for any $n\geq{0}$, 1st player
responds with $(0,n+1)$.
\end{itemize}
And the above procedure should be repeated for all consecutive moves.
Notice that if player 2 had a valid move, so does player 1, unless
player 2 picked $(0,0)$ and lost.

Furthermore, there are no other winning strategies for player 1,
because if she starts with any other legal move, player 2 will be able
to adopt either of the two winning strategies and win for sure:
\begin{itemize}
\item
If player 1 picks some $(m,n)$ where $m,n\geq{1}$ and
$(m,n)\neq(1,1)$, then player 2 can pick $(1,1)$ next, and then use
the first strategy to win against player 1.
\item
If player 1 picks some $(0,n)$ or $(n,0)$ where $n\geq{3}$, then
player 2 can respectively pick $(0,2)$ or $(2,0)$ next, and then use
the second strategy to win against player 1.
\item
If player 1 picks $(1,0)$ or $(0,1)$ then player 2 picks the other one
and wins.
\end{itemize}
}

\eparts

At any point in the game, a valid move $(a,b)$ is said to be
\emph{bounded} iff both $a$ is bounded above by the $x$-coordinate of
some previous move and $b$ is bounded above by the $y$-coordinate of
some previous move.  For example, if the previous moves have been
$(1,3),(3,1), (2,2)$, then there are ten possible bounded moves:
$\{(1,2),(2,1),(1,1),(0,3),(0,2),(0,1),(0,0),(1,0),\\(2,0),(3,0)\}$.
There is also an infinite number of possible unbounded moves at this
point, namely, any move with one coordinate equal to $0$ and the other
larger than $3$.

For any state $S$ of the game after the first move, let $X(S)$ be the
minimum of the $x$-coordinates of the previous moves, $Y(S)$ be the
minimum of the $y$-coordinates, and $B(S)$ be the number of possible
bounded moves.  Define the \emph{measure}, $M(S)$, of the state to be the
triple $(X(S), Y(S), B(S))$.

Define the following ordering on triples of natural numbers:
\[(x,y,k) < (x',y',k') \iff [(x< x') \vee (x= x' \wedge
y < y') \vee (x=x' \wedge y = y' \wedge k < k')\]

\bparts

\ppart Prove that any nonempty subset of
$\naturals^3$ has a least element under the above ordering.

\solution{
Let $S$ be some nonempty subset of $\naturals^3$.  Let
$S_x=\{x\mid\exists_{y,z}\,\,(x,y,z)\in{S}\}$.  Then
$S_x\subset\naturals$, and so by the well-ordering principle, there is
a smallest element $x_{min}$ in $S_x$.  Now take a set
$S_{y}=\{y\mid\exists_{z}\,\,(x_{min},y,z)\in{S}\}$.  Since
$S_{y}\subseteq\naturals$, and it is not empty, it has a smallest
element $y_{min}$.  Similarly, the set
$S_{z}=\{z\mid(x_{min},y_{min},z)\in{S}\}$ has a smallest element
$z_{min}$.

Clearly, $(x_{min},y_{min},z_{min})$ is the smallest element in $S$.
If there was some smaller element $(x',y',z')$ in $S$, then:
\begin{itemize}
\item
If $x'<x_{min}$ then $x'\neq{x_{min}}$ would be the smallest element
in $S_x$.  Impossible.
\item
If $x'=x_{min}$ and $y'<y_{min}$ then $y'\neq{y_{min}}$ would be the
smallest element in $S_{y}$.  Impossible.
\item
If $x'=x_{min}$, $y'=y_{min}$ and $z'<z_{min}$ then $z'\neq{z_{min}}$
would be the smallest element in $S_z$.  Impossible.
\end{itemize}
}

\ppart Conclude that the game always terminates,
regardless of the players' strategy.

\solution{
We will show below that the measure $M(S)=(X(S),Y(S),B(S))$ 
decreases with every move
according to the ordering in $\naturals^3$ defined above.
%On the other hand $M(S)$ cannot pass below $(0,0,0)$ because the
%minimum x coordinate, the minimum y coordinate and the number of
%bounded points cannot be negative.  
%Therefore the game has to
%terminate.

Assume by
contradiction that for some move leading from state $S=(x,y)$ to state
$S'=(x',y')$, we have that $M(S')\geq{M(S)}$.  There are three cases
in which ${M(S)}\leq{M(S')}$ could be true:
\begin{enumerate}
\item
$X(S)<X(S')$, which would mean that the minimum of the x-coordinates
has increased, which is impossible (the minimum of a set to which we
are adding some new element cannot increase).
\item
$X(S)=X(S')\,\wedge\,Y(S)<Y(S')$, which would mean that the minimum of
the y-coordinates has increased, which is impossible for the same
reason as above.
\item
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$.  Let
$\{(x_1,y_1),\ldots,(x_n,y_n)\}$ be the points that were picked up to
move $S\,\rightarrow\,S'$ (i.e., the points that constitute state $S$),
and let $(x',y')$ be the new point.  If $X(S)=X(S')$ and $Y(S)=Y(S')$,
then $x'\geq\min_i\{x_i\}\,\wedge\,y'\geq\min_i\{y_i\}$.

We first show that $(x',y')$ must be a bounded point in state $S$.
Assume otherwise.  That would mean that either $x'$ or $y'$ were not
bounded in state $S$.  Without loss of generality, assume $x'$ was not
bounded, i.e., that $x'>{x_i}$ for all $i$.  On the other hand, we
know that $y'\geq{}y_j=\min_i\{y_i\}$.  But then $y_j\leq(y')$ and
$x_j<x'$ which would make $(x',y')$ an illegal move.  Hence $(x',y')$
must be a bounded point of state $S$.

Now we show that since $(x',y')$ is bounded in $S$, state
$S'=S\cup\{(x',y')\}$ must have fewer bounded points than $S$, i.e.,
that $B(S')<B(S)$.  This will finish the proof that
$X(S)=X(S')\,\wedge\,Y(S)=Y(S')\,\wedge\,B(S)\leq{B(S')}$ cannot be
true.  

Notice that a point $(x,y)$ is bounded in state $S=\{x_i,y_i\}$ iff it
is a valid move and $x\leq\max_S\{x_i\}$ and $y\leq\max_S\{y_i\}$.
Since, if $(x',y')$ is bounded in $S$ then the maximal x and y
coordinates do not change from $S$ to $S'$.  Consequently, if
$x\leq\max_{S'}\{x_i\}\,\wedge\,y\leq\max_{S'}\{y_i\}$ then
$x\leq\max_S\{x_i\}\,\wedge\,y\leq\max_S\{y_i\}$.  Also, if a point
$(x,y)$ is valid in $S'$, it is also valid in $S$ (it clearly follows
from the fact that $S\subset{S'}$).  From these two facts it follows
that if a point is bounded in $S'$, it is also bounded in $S$.  In
other words, the set ${\cal B}'$ of bounded points of $S'$ is a subset
of ${\cal B}$, the set of bounded points of $S$.  Since the latter is
a finite set\footnote{
%
After the first move, the set of bounded points is always finite,
because for whatever values $x_{max},y_{max}$, there are finite number
of pairs $(x,y)\in\naturals^2$ s.t. $x\leq{x_{max}}$ and
$y\leq{y_{max}}$.
%
} and ${\cal B}'\subset\{{\cal B}\setminus(x',y')\}$, it follows that
$B(S')=|{\cal B}'|<|{\cal B}|=B(S)$.
\end{enumerate}
This proves that measure $M(S)$ always decreases and hence finishes
the proof that the game always terminates.
}
\eparts

\problem \textbf{Summations}

Recall that $H_n$ is the $n\kth$ harmonic number, i.e., \[
H_n=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{n} \]

\bparts

\ppart Rosen \S 1.7 exercise 21 (Do not quote the answer from the back, and
instead explicitly show the steps involved in calculating that answer.)

\solution{
(i) \begin{eqnarray*}
\sum_{k=1}^n 2k-1 &=& \sum_{k=1}^n k^2-(k-1)^2\\ 
                  &=& n^2 - (n-1)^2 + (n-1)^2 - (n-2)^2+(n-2)^2 - (n-3)^2 \\ 
                   && + \cdots + 1^2 - 1^2 + 0^2 \\
                  &=& n^2
\end{eqnarray*}

(ii) $\sum_{k=1}^n 2k-1=-n + 2\sum_{k=1}^n k$.  This implies that
\begin{eqnarray*}
\sum_{k=1}^n k & = & \frac{1}{2}\left[n + \sum_{k=1}^n 2k-1\right]\\
               & = & \frac{1}{2}(n + n^2)\\
               & = & \frac{1}{2}n(1+n)
\end{eqnarray*}
\hfill$\Box$
}

\eparts

Find a closed form for each of the following:

\bparts

\ppart $\sum_{k=0}^{\infty} i^k/2^{k/4}$, where $i$ is $\sqrt{-1}$.

\solution{Note that we can separate this sum into several pieces:
\begin{center}
\begin{tabular}{rl}
(1) & $1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots +$ \\
(2) & $\frac{i}{2^{1/4}} + \frac{i}{2^{5/4}} + \frac{i}{2^{9/4}} +
\frac{i}{2^{13/4}} + \cdots +$ \\
(3) & $\frac{-1}{2^{2/4}} + \frac{-1}{2^{6/4}} + \frac{-1}{2^{10/4}} +
\frac{-1}{2^{14/4}} + \cdots +$ \\
(4) & $\frac{-i}{2^{3/4}} + \frac{-i}{2^{7/4}} + \frac{-i}{2^{11/4}} +
\frac{-i}{2^{15/4}} + \cdots$
\end{tabular}
\end{center}
You should recognize the first summation: it converges to 2.  The
second summation is therefore simply $\frac{i}{2^{1/4}}$ times the
first summation, leaving $2^{3/4}i$.  Similarly, the third and fourth
summations are $-\sqrt{2}$ and $-2^{1/4}i$, respectively.  The total is
then $(2 - \sqrt{2}) + i(2^{3/4}-2^{1/4})$, or
$(1+2^{-1/4}i)(2-\sqrt{2})$.\hfill$\Box$

}

\ppart $\sum_{k=1}^{\infty} 1/k(k+n)$ (Your
solution may involve the harmonic number function.)

\solution{Note by partial fractions that
\[ \frac{n}{k(k+n)}=\frac{1}{k}-\frac{1}{k+n} \]
Let $K>n$, then 
\[
\sum_{k=1}^K \left(\frac{1}{k}-\frac{1}{k+n}\right) = \sum_{k=1}^n
\frac{1}{k}-\sum_{k=K+1}^{K+n}\frac{1}{k}
\]
But 
\[
\sum_{k=K+1}^{K+n}\frac{1}{k}\le \frac{n}{K+1}
\] 
Therefore 
\[
\lim_{K\to\infty} \sum_{k=K+1}^{K+n}\frac{1}{k} = 0
\] 
Hence 
\[
\lim_{K\to\infty} \sum_{k=1}^K \left(\frac{1}{k}-\frac{1}{k+n}\right) = H_n
\]
i.e.
\[
\sum_{k=1}^{\infty} \frac{1}{k(k+n)} = \frac{H_n}{n}
\]
%\begin{eqnarray*}
%\sum_{k=1}^{\infty} \frac{1}{k(k+n)} &=& \frac{1}{n}\sum_{k=1}^{\infty}
%\left[\frac{1}{k}-\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{\infty}\frac{1}{k} -
%\sum_{k=1}^{\infty}\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{n}\frac{1}{k} +
%\sum_{k=n+1}^{\infty}\frac{1}{k} - 
%\sum_{k=1}^{\infty}\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{n}\frac{1}{k} +
%\sum_{k=n+1}^{\infty}\frac{1}{k} - 
%\sum_{k=n+1}^{\infty}\frac{1}{k}\right] \\
%&=& \frac{1}{n}\sum_{k=1}^{n}\frac{1}{k} \\
%&=& \frac{H_n}{n}
%\end{eqnarray*}
%\hfill$\Box$
}

\ppart $\sum_{i=1}^\infty\sum_{j=1}^\infty ix^iy^{i+2j}$

\solution{\begin{eqnarray*}
\sum_{i=1}^\infty\sum_{j=1}^\infty ix^iy^{i+2j} & = &
\sum_{i=1}^\infty\left[i(xy)^i\left(\sum_{j=1}^\infty
y^{2j}\right)\right] \\
&=& \sum_{i=1}^\infty\left[i(xy)^i\left(\sum_{j=1}^\infty
(y^2)^j\right)\right] \\
&=&
\sum_{i=1}^\infty\left[i(xy)^i\left(\frac{y^2}{1-y^2}\right)\right] \\ 
&=&
\frac{y^2}{1-y^2}\sum_{i=1}^\infty\left[i(xy)^i\right] \\ 
&=&
\frac{y^2}{1-y^2}\cdot\frac{xy}{(1-xy)^2} \\ 
&=& \frac{xy^3}{(1-y^2)(1-xy)^2}
\end{eqnarray*}
}

\eparts

Find asymptotically tight bounds\footnote{We say that function $f$
provides an asymptotically tight bound for a function $g$ if $lim_{n \to
\infty} f(n)/g(n) = 1$.  That is, $f \sim g$ using the notation from
Lecture Notes 8, \S 2.4.} for the following:

\bparts
\ppart $\sum_{k=1}^{n} k^4$

\solution{\begin{eqnarray*}
\sum_{k=1}^{n+1} k^4 &\leq& \int_{1}^{n+2} x^4\ dx \\
&=&\frac{(n+2)^5-1}{5}\\
&\sim&\frac{n^5}{5}
\end{eqnarray*}
\begin{eqnarray*}
\sum_{k=1}^{n+1} k^4 &\geq& \int_{0}^{n+1} x^4\ dx \\
&=&\frac{(n+1)^5}{5}\\
&\sim&\frac{n^5}{5}
\end{eqnarray*}\hfill$\Box$}

\ppart $\sum_{k=1}^{n} e^{\sqrt{k}}/\sqrt{k}$

\solution{Note that with $u=\sqrt{x}$, $du=\frac{1}{2 \sqrt{x}}\ dx$.
So,
\begin{eqnarray*}
\sum_{k=1}^{n} \frac{e^{\sqrt{k}}}{\sqrt{k}} &\leq& \int_{1}^{n+1}
\frac{e^{\sqrt{x}}}{\sqrt{x}}\ dx \\
&=& 2(e^{\sqrt{n+1}}-e)\\
&\sim& 2 e^{\sqrt{n}}
%\\
%&\leq& e^{\sqrt{n}+1}-e \\
%&=& e\cdot e^{\sqrt{n}}-e \\
%&\sim& e^{\sqrt{n}}
\end{eqnarray*}
To see why the last line holds, notice that
$\sqrt{n+1}-\sqrt{n}=\frac{1}{\sqrt{n+1}+\sqrt{n}}$,
so $\sqrt{n+1}-\sqrt{n}\to 0$ as $n\to\infty$. Thus
$\lim_{n\to\infty} \frac{e^{\sqrt{n+1}}}{e^{\sqrt{n}}} = 1$.\\
Finally, 
\begin{eqnarray*}
\sum_{k=1}^{n} \frac{e^{\sqrt{k}}}{\sqrt{k}} &\geq& \int_{0}^{n}
\frac{e^{\sqrt{x}}}{\sqrt{x}}\ dx \\
&=& 2 e^{\sqrt{n}}-2\\
&\sim& 2 e^{\sqrt{n}}.
\end{eqnarray*}\hfill$\Box$}

\eparts
%Alantha's problems.

\problem {\bf Linked lists}

You are given a one-way linked list with starting link $l_0$.  For any
link, $l$, we let $S(l)$ denote the next link in the list after $l$. If
$S(l) = \texttt{NULL}$, then link $l$ is the last link on the list.  But
the list may link back to itself (that is, it may be that $S(l_1)=S(l_2)$
for some links $l_1 \neq l_2$), in which case there is no last link
because the list ends in a cycle.  To determine whether or not there is a
cycle, you could follow the links down the list recording the links
encountered while checking to see if a link is ever revisited, but this
could take a lot of memory and time.  So you use the following procedure
to detect cycles:

\begin{verbatim}
a := l_0;
b := l_0;
while ((S(a) != NULL) and (S(b) != NULL) and (S(S(b)) != NULL))
{
    a := S(a);
    b := S(S(b));
    if a = b
        return "CYCLE"
};
return "NO CYCLE"
\end{verbatim}

\noindent
Prove that this procedure terminates and produces the correct answer.

\solution{ If the list has no cycles, then within $n/2$ steps, where $n$
is the length of the list, either \texttt{S(b)} or \texttt{S(S(b))} will
be \texttt{NULL}, so the process will break from the while loop and return
\texttt{NO CYCLE}.

\hspac
\noindent
If the list does contain a cycle, then eventually both markers \texttt{a}
and \texttt{b} will be stuck in the cycle.  Let $d_j$ denote the distance
measured clockwise from \texttt{b} to \texttt{a} at the $j^{th}$ execution
of the while loop.  (Assume the markers are moving around the cycle in the
clockwise direction.) If $d_j$ = 0, then \texttt{a} = \texttt{b}, so the
process terminates and outputs \texttt{CYCLE}.  Otherwise, note that at
each execution of the while loop, this distance decreases by exactly one,
so after $d_j$ steps, the process outputs \texttt{CYCLE} and terminates.
}

\problem{\bf Mystery Problem}

Given a list of numbers $A[1], \dots,A[n]$, sorted in increasing order,
and a number $a$, consider the following procedure which takes as
arguments natural numbers $i,j \in \set{1,\dots,n}$ such that $i \leq j$:

\begin{verbatim}
Proc(i, j):
    start  := i;
    end    := j;
    middle := start + quotient((end - start)/2);
    if A[middle] = a
        return middle;
    if (start = middle)
        return "NOT FOUND";
    if A[middle] > a
        Proc(start, middle)
    else
        Proc(middle+1, end)
\end{verbatim}

\noindent
What does $\mbox{\texttt{Proc}}(i, j)$ do?  Prove your answer.
Note that {\tt start}, {\tt middle}, and {\tt end} are always integers.

\solution{

If $a$ is in the list, say $a= A[k]$, then $\mbox{\texttt{Proc}}(1,n)$
returns $k$.  If $a$ is not in the list, then $\mbox{\texttt{Proc}}(1,n)$
returns \texttt{NOT FOUND}.

To prove this, we prove more generally that for any $1 \leq i \leq j \leq
n$, if $a$ is in the list $A[i],\dots,A[j]$---say $a= A[k]$---then
$\mbox{\texttt{Proc}}(i,j)$ returns $k$.  And if $a$ is not in the list
$A[i],\dots,A[j]$, then $\mbox{\texttt{Proc}}(i,j)$ returns \texttt{NOT
FOUND}.  The proof is by induction on the value of $j-i$.

If $j-i = 0$, that is $j = i$, then in the call
$\mbox{\texttt{Proc}}(i,j)$, the initial value of \texttt{middle} will be
$i$, and the call will return $i$ or \texttt{NOT FOUND} according to
whether $a = A[i]$, that is, whether $a$ is in the list $A[i]$.  So in the
base case, the call behaves according to thte hypothesis.

Now suppose $j-i > 0$.  In the call $\mbox{\texttt{Proc}}(i,j)$, let $k$
be the initial value of \texttt{middle}.  From the assignment which
defines the initial value of \texttt{middle}, we conclude that $i\leq k <
j$.  If $a = A[k]$, then the call will return $k$; but in this case, $a$
is indeed in the list $A[i],\dots,A[j]$, so this is the return behavior
specified by the induction hypothesis for $j-i$.  Next, if $A[k]>a$, then
the call of $\mbox{\texttt{Proc}}(i,j)$ will return the same result as the
call $\mbox{\texttt{Proc}}(i,k)$.  But now $k-i < j - i$ so by induction,
this call returns the index of $a$ if $a$ is in the list $A[i], \dots,
A[k]$, and returns \texttt{NOT FOUND} otherwise.  But since $A[k]>a$, it
follows that $a$ is in the list $A[i], \dots, A[j]$ iff it is in the list
$A[i], \dots, A[k]$, so the answer returned by the call
$\mbox{\texttt{Proc}}(i,k)$ is the one required by the induction
hypothesis for $j-i$.  A similar argument verifies the induction
hypothesis for $j-i$ in the case that $A[k]<a$.

}

\end{problems}

\end{document}

