\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}

\begin{document}
\noindent { \bf Problem 5 correction}

The following code estimates the value of \( \frac{1}{1-x/2} \) to
within an additive error of $1/1024$ for $0< x < 1 $.  Prove that it
is correct.

\begin{verbatim}
estimate(x) 
{ 
  Fprev = 0;
  Fnext = 1;
  while (Fnext - Fprev > 1/1024) {
    Fprev = Fnext;
    Fnext = (Fprev * x / 2) +1;
  }
  return(Fnext);
}
\end{verbatim}

\begin{theorem}
In the $n$th step of the algorithm we have: \\
Fprev $= \sum_{i=0}^{n-1}{(\frac{x}{2})^i} $ \\
Fnext $= \sum_{i=0}^{n}(\frac{x}{2})^i $ \\
\end{theorem}

\begin{proof}
BASE CASE: In the $0$th step Fprev $=0= \sum_{i=0}^{-1}{(\frac{x}{2})^i} $,
Fnext $=1= \sum_{i=0}^{0}{(\frac{x}{2})^i}$. \\

INDUCTIVE STEP: At the $(n+1)$th step we have:

Fprev := Fnext =  $= \sum_{i=0}^{n}{(\frac{x}{2})^i} $

Fnext := (Fprev$*x/2)+1 = x \sum_{i=0}^{n}{(\frac{x}{2})^i}/2 +1 =
\sum_{i=0}^{n+1}{(\frac{x}{2})^i}$.

\end{proof}

From the above theorem, termination follows trivially because
Fnext - Fprev $=(\frac{x}{2})^n$ becomes less than 1/1024 for sufficiently
high $n$.  

To see that the algorithm computes $\frac{1}{1-x/2}$ within an error of
1/1024, note that 

\begin{math}
\frac{1}{1-x/2} = \sum_{i=0}^{\infty}{(\frac{x}{2})^i} =
\sum_{i=0}^{n}{(\frac{x}{2})^i} + \frac{(x/2)^{n+1}}{1-x/2} = Fnext + error
\end{math} 

But, $error= \frac{(x/2)^{n+1}}{1-x/2} = \frac{(x/2)^n}{2/x-1} $.  We can show
that $\frac{1}{(2/x)-1} < 1$ (reduce it to $x<1$), so 
$error= \frac{(x/2)^n}{2/x-1} < 
(x/2)^n = Fnext - Fprev < 1/1024$ at
termination.


\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
